https://leetcode.com/problems/path-sum-ii/
給定一個(gè)二叉樹(shù)，給定一個(gè)int值sum氮趋，求二叉樹(shù)根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑和為sum的所有情況
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]
]
DFS
- 終止條件是
if (val == sum && root.left == null && root.right == null)闯捎，如果用root == null && sum ==0會(huì)出現(xiàn)在左右子樹(shù)遍歷兩次結(jié)果
public List<List<Integer>> pathSum2(TreeNode root, int sum) {
List<Integer> out = new ArrayList<Integer>();
List<List<Integer>> res = new ArrayList<List<Integer>>();
pathSum2Helper(root, sum, out, res);
return res;
}
public void pathSum2Helper(TreeNode root, int sum, List<Integer> out, List<List<Integer>> res) {
if (root == null) {
return;
}
int val = root.val;
if (val == sum && root.left == null && root.right == null) {
out.add(val);
res.add(new ArrayList<Integer>(out));
out.remove(out.size() - 1);
return;
}
out.add(val);
pathSum2Helper(root.left, sum - val, out, res);
pathSum2Helper(root.right, sum - val, out, res);
out.remove(out.size() - 1);
}
