题目信息

  • 题目：剑指 Offer 34. 二叉树中和为某一值的路径

  • 时间： 2020-09-07

  • 题目链接：Leetcode

  • tag：深度优先搜索 回溯法

  • 难易程度：中等

  • 题目描述：

    输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:

给定如下二叉树，以及目标和 sum = 22，

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

返回：

1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]

提示

1
1.节点总数<=10000

解题思路

本题难点

本问题是典型的二叉树方案搜索问题，使用回溯法解决，其包含 先序遍历 + 路径记录 两部分。

具体思路

  • 先序遍历：按照 “根、左、右” 的顺序，遍历树的所有节点。
  • 路径记录： 在先序遍历中，记录从根节点到当前节点的路径。当路径为 ① 根节点到叶节点形成的路径 且 ② 各节点值的和等于目标值 sum 时，将此路径加入结果列表。

值得注意的是，记录路径时若直接执行 res.append(path) ，则是将 path 对象加入了 res ；后续 path 改变时， res 中的 path 对象也会随之改变。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  //结果列表 res
    List<List<Integer>> res = new LinkedList<>();
  //路径列表 path
    LinkedList<Integer> path = new LinkedList<>(); 
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root,sum);
        return res;
    }

    void recur(TreeNode root,int tar){
      //终止条件： 若节点 root 为空，则直接返回。
        if(root == null){
            return;
        }
      //路径更新： 将当前节点值 root.val 加入路径 path 
        path.add(root.val);
      //目标值更新： tar = tar - root.val（即目标值 tar 从 sum 减至 0 ）；
        tar -= root.val;
      //路径记录： 当 ① root 为叶节点 且 ② 路径和等于目标值 ，则将此路径 path 加入 res 。
        if(tar == 0 && root.left == null && root.right == null){
            res.add(new LinkedList(path));
        }
      //先序遍历： 递归左 / 右子节点。
        recur(root.left,tar);
        recur(root.right,tar);
      //路径恢复： 向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.removeLast() 。
        path.removeLast();
    }
}

复杂度分析：

  • 时间复杂度 O(N) ： N 为二叉树的节点数，先序遍历需要遍历所有节点。
  • 空间复杂度 O(N) ： 最差情况下，即树退化为链表时，path 存储所有树节点，使用 O(N) 额外空间。