leetcode113.Path Sum II

发表于 更新于 分类于 ，

题目要求

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]

从树中找到所有符合条件的从根节点到叶节点路径，条件即为树上所有节点值的和等于目标值。
Path Sum I可以参考这篇博客

思路和代码

其实这里本质上的思路并没有改变，还是采用深度优先算法，采用自顶向下递归的方式将符合条件的结果放入结果集中。

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
public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    pathSum(root, sum, new ArrayList<Integer>(), result);
    return result;
}

public void pathSum(TreeNode root, int sum, List<Integer> path, List<List<Integer>> result){
    if(root==null) return;
    sum -= root.val;
    if(isLeaf(root) && sum==0){
        path.add(root.val);
        result.add(new ArrayList<Integer>(path));
        path.remove(path.size()-1);
        return;
    }
    path.add(root.val);
    pathSum(root.left, sum, path, result);
    pathSum(root.right, sum, path, result);
    path.remove(path.size()-1);
    
    
}

private boolean isLeaf(TreeNode node){
    return node!=null && node.left==null && node.right==null;
}