解题思路

这道题是“112. 路径总和”的升级版本，在这道题我们需要把所有可能的解都存储下来并返回。为了记录路过的节点，我们使用一个变量List path来存储路过的节点的值。我们将每个路过的节点的值都放入path中，如果走到叶节点发现是一条可行的路径（节点值之和等于sum），我们就复制path数组，然后放入到结果变量List> ans。当从节点返回时，我们需要回溯以保证path变量的正确性。

上面的思路可以使用二叉树的先序遍历来实现。我们用题目给的case来描述执行过程：我们不断地向左走，找到一条路径”5->4->11->7”，path变量的内容依次变为[5], [5, 4], [5, 4, 11], [5, 4, 11, 7]。然后我们发现这条路径的和不等与sum，我们从节点7回溯，path变量从[5,4,11,7]变为[5,4,11]，回到节点11走向它的右子树，此时path变量为[5,4,11,2]，发现路径和与sum相等，复制path数组的到ans。因为我们需要复用path数组，所以不能直接调用ans.add(path)，而是应该调用ans.add(new ArrayList<>(path))，创建path的副本并加入到ans中。

假设我们不考虑path数组复制的过程，那么时间复杂度为O(n)（因为要遍历所有节点），空间复杂度为O(n)（空间为调用栈开销，当树为链式）。

  public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        helper(root,sum,res,new ArrayList<>());
        return res;
    }
    private void helper(TreeNode node,int sum,List<List<Integer>> ans,List<Integer> path){
        if (node == null)
            return;
        sum -= node.val;
        path.add(node.val);
        if (node.left == null && node.right == null) {
            if (sum == 0)
                ans.add(new ArrayList<>(path));
        }else{
            helper(node.left,sum,ans,path);
            helper(node.right,sum,ans,path);
        }
        path.remove(path.size()-1);
    }