Haiyang Yu's Blog
0%

发表于 更新于 Valine：
本文字数： 1.5k 阅读时长 ≈ 1 分钟

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

示例:
给定如下二叉树，以及目标和 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]
]

提示：

节点总数 <= 10000

DFS

这题按照一般的套路还不行, 我一开始想用root == null作为终止的条件,但是碰见那种只有一个节点的树就失灵了

例如

1
2
3
4
5
     1
    / \
   2   null
  / \
null null

如果是root == null这一个终止条件, 那么这就有3条路, 1 -> null,1 -> 2 -> leftNull, 1->2->RightNull

如果target = 1, 原来的树没有这样的路径, 但是这样会找出来一条路径1->null

如果target = 3, 则会找出2条相同的路径来, 1->2和1->2

所以DFS终止条件是root.left == null && root.right == null

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
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null){
            return ans;
        }
        List<Integer> curr = new ArrayList<>();
        int currSum = 0;
        DFS(root, sum, ans, curr, currSum);
        return ans;
    }
    private void DFS(TreeNode root, int sum, List<List<Integer>> ans, List<Integer> curr, int currSum){
        if(root.left == null && root.right == null){
            currSum += root.val;
            if(currSum == sum){
                curr.add(root.val);
                ans.add(new ArrayList<>(curr));
                curr.remove(curr.size() - 1);
            }
            return;
        }
        else{
            currSum += root.val;
            curr.add(root.val);
            if(root.left != null)
                DFS(root.left, sum, ans, curr, currSum);
            if(root.right != null)
                DFS(root.right, sum, ans, curr, currSum);
            currSum -= root.val;
            curr.remove(curr.size() - 1);
        }
    }
}