LeetCode 113 Path Sum II

解题思路：

这里需要传入一个全局量来记录数据。

就好比学校评比卫生标兵寝室～于是乎宿管大妈带着个计分的表格开始检查卫生，从一楼记到四楼，每层都记录数据。

从无到有，越积越多。分数过低的，不符合条件的直接从计分表里划出去，不再考虑。

 1 public List<List<Integer>> pathSumII(TreeNode root, int sum) {
 2     List<List<Integer>> res = new ArrayList<>();
 3     List<Integer> subRes = new ArrayList<>();
 4     if (root == null) {
 5         return res;
 6     }
 7     helper(root, subRes, res, sum);
 8     return res;
 9 }
10 
11 private void helper(TreeNode root, List<Integer> subRes, List<List<Integer>> res, int sum) {
12     if (root == null) {
13         return;
14     }
15     if (root.left == null && root.right == null) {
16         if (root.val == sum) {
17             subRes.add(root.val);
18         res.add(new ArrayList<Integer>(subRes));
19         subRes.remove(subRes.size() - 1);
20         }
21         return;
22 }
23 
24 subRes.add(root.val);
25 helper(root.left, subRes, res, sum - root.val);
26 helper(root.right, subRes, res, sum - root.val);
27     //Remove的是把当前层的root从subRes中删除
28     subRes.remove(subRes.size() - 1);
29 }

这里，subRes是记录从老祖宗root到当前层的节点node走过的路径， res是全局用来存储结果的变量。