113 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]
]
Company Tags: Bloomberg
分析&代码
和112 Path Sum一样,就是多了一个记录的功能
注意最后的一个叶节点的结果添加的时候,不要加到curList里面,如果加了,return之前要退掉
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
sumPath(root, sum, res, new ArrayList<Integer>());
return res;
}
private void sumPath(TreeNode root, int target, List<List<Integer>> res, List<Integer> cur) {
if(root == null) {
return;
}
if(root.left == null && root.right == null) {
if(root.val == target) {
List<Integer> curRes = new ArrayList<>(cur);
curRes.add(root.val);
res.add(curRes);
}
return;
}
cur.add(root.val);
sumPath(root.left, target - root.val, res, cur);
sumPath(root.right, target - root.val, res, cur);
cur.remove(cur.size() - 1);
}