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]
]
Analysis
DFS problem
Code
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(root == null) {return result;}
List<Integer> list = new ArrayList<Integer>();
dfs(root, sum, list, result);
return result;
}
private void dfs(TreeNode root, int sum, List<Integer> list, List<List<Integer>> result){
if (root == null) {return;}
list.add(root.val);
if (root.left == null && root.right == null && root.val == sum){
result.add(new ArrayList<Integer>(list));
//IMPORTANT!! Easy to forget!
list.remove(list.size()-1);
return;
}
dfs(root.left, sum-root.val, list, result);
dfs(root.right, sum-root.val, list, result);
list.remove(list.size()-1);
}
}
Note
- 在code中把list加入到result后,注意要remove最后一个element。注意在return前要把之前加入list的删除。
- result加入list记住要copy一个新的list加入,不然之后的操作会改变list的值。
- list可以加入的条件是到达leaf node并且sum为target