• Path Sum II

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,
1. 5
2. / \
3. 4 8
4. / / \
5. 11 13 4
6. / \ / \
7. 7 2 5 1

return
1. [
2. [5,4,11,2],
3. [5,8,4,5]
4. ]

Solution:
1. /*
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. * int val;
5. * TreeNode left;
6. * TreeNode right;
7. * TreeNode(int x) { val = x; }
8. * }
9. /
10. public class Solution {
11. public List<List> pathSum(TreeNode root, int sum) {
12. List<List> res = new ArrayList<>();
13. List sol = new ArrayList<>();
14. 15. helper(root, sum, sol, res);
16. 17. return res;
18. }
19. 20. void helper(TreeNode root, int sum, List sol, List<List> res) {
21. if (root == null)
22. return;
23. 24. sol.add(root.val);
25. 26. if (root.left == null && root.right == null && root.val == sum) {
27. res.add(new ArrayList<>(sol));
28. } else {
29. helper(root.left, sum - root.val, sol, res);
30. helper(root.right, sum - root.val, sol, res);
31. }
32. 33. sol.remove(sol.size() - 1);
34. }
35. }