二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 sum = 22，

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2   5   1

返回:

[
[5,4,11,2],
[5,8,4,5]
]

提示：

1. 节点总数 <= 10000

实际上就是先序遍历，记录路径，回退的时候记得remove掉叶子

---

解法1 ：7ms

class Solution {
   List<List<Integer>> result = new ArrayList<>();
    int sum; 
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        this.sum = sum;
        lookSum(root, new ArrayList<>());
        return result;
    }

    public void lookSum(TreeNode root,List<Integer> integerList){
       if(root == null){
            return;
        }
        //因为Java是传递的引用,我们不能共同用一个list。而是每次new一个，复用之前的路径
        ArrayList<Integer> integerArrayList = new ArrayList<>(integerList);
        integerArrayList.add(root.val);
        if(root.left == null && root.right == null){
            if (integerArrayList.stream().mapToInt(Integer::intValue).sum() == sum) {
                result.add(integerArrayList);
            }
            return;
        }
        lookSum(root.left, integerArrayList);
        lookSum(root.right, integerArrayList);
    }
}

执行用时：7 ms
内存消耗：42.2 MB

缺点：

• 每次都new了
• 每次都计算了数组了和了
• stream 是要慢一点

---

优化 ：3ms

class Solution {
   List<List<Integer>> result = new ArrayList<>();
    int sum; 
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        this.sum = sum;
        lookSum(root, new ArrayList<>(),0);
        return result;
    }

    public void lookSum(TreeNode root,List<Integer> integerList,int cur_sum){
        if(root == null){
            return;
        }
        ArrayList<Integer> integerArrayList = new ArrayList<>(integerList);
        integerArrayList.add(root.val);
        if(root.left == null && root.right == null){
            if (cur_sum+root.val == sum) {
                result.add(integerArrayList);
            }
            return;
        }
        lookSum(root.left, integerArrayList,cur_sum+root.val);
        lookSum(root.right, integerArrayList, cur_sum + root.val);
    }
}

执行用时：3 ms
内存消耗：42.9 MB
缺点

• 不用每次都计算和了，把和标记下
• 每次都new有点不划算

---

优化 ：1ms

class Solution {
   List<List<Integer>> result = new ArrayList<>();
    int sum; 
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        this.sum = sum;
        lookSum(root, new ArrayList<>(),0);
        return result;
    }

    public void lookSum(TreeNode root,List<Integer> integerList,int cur_sum){
        if(root == null){
            return;
        }
        integerList.add(root.val);
        if(root.left == null && root.right == null){
            if (cur_sum+root.val == sum) {
                result.add(new ArrayList<>(integerList));
            }
            //回退记得remove
            integerList.remove(integerList.size() - 1);
            return;
        }
        lookSum(root.left, integerList,cur_sum+root.val);
        lookSum(root.right, integerList, cur_sum + root.val);
        //回退记得remove
        integerList.remove(integerList.size() - 1);
    }
}

执行用时：1 ms
内存消耗：39.7 MB