![](https://www.dazhuanlan.com/webchat.jpg)
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
Note
A leaf is a node with no children.
Example
Given the below binary tree and sum = 22,
1 2 3 4 5 6 7
|
5 / 4 8 / / 11 13 4 / / 7 2 5 1
|
Return:
1 2 3 4
|
[ [5,4,11,2], [5,8,4,5] ]
|
Code
1 2 3 4 5 6
|
public class { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> result = new ArrayList<>();
pathSumHelper(result, new ArrayList<>(), root, sum);
return result; }
private void pathSumHelper(List<List<Integer>> result, List<Integer> path, TreeNode root, int sum) { if (root == null) return; path.add(root.val);
if (root.left == null && root.right == null) { if (root.val == sum) result.add(new ArrayList<>(path)); }
pathSumHelper(result, path, root.left, sum - root.val); pathSumHelper(result, path, root.right, sum - root.val); path.remove(path.size() - 1); }
|
近期评论