Path Sum II
Definition
Similar to Sum Root to Leaf Numbers
pathSum(node) = [] [ empty tree ]
parent_list(node) union node.val [ node is leaf ]
pathSum(node.left) unoin pathSum(node.right) [ otherwise ]
parent_list(node) = [] [ node is root ]
parent_list(parent_node) union parent_node.val [ otherwise ]
Source code Read on Github
1 /**
2 * Definition for binary tree
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
12 void addIfNotEmpty(List<List<Integer>> rt, List<List<Integer>> l){
13 if(!l.isEmpty()){
14 rt.addAll(l);
15 }
16 }
17
18 List<List<Integer>> pathSum(TreeNode root, int sum, List<Integer> parents) {
19 List<List<Integer>> rt = new ArrayList<List<Integer>>();
20
21 if(root == null) return rt;
22
23 ArrayList<Integer> p = new ArrayList<Integer>(parents);
24 p.add(root.val);
25
26 if(root.left == null & root.right == null){
27 if(root.val == sum){
28 rt.add(p);
29 }
30
31 return rt;
32 }
33
34 addIfNotEmpty(rt, pathSum(root.left, sum - root.val, p));
35 addIfNotEmpty(rt, pathSum(root.right, sum - root.val, p));
36
37 return rt;
38 }
39
40 public List<List<Integer>> pathSum(TreeNode root, int sum) {
41
42 return pathSum(root, sum, new ArrayList<Integer>());
43 }
44 }