Path Sum II

https://leetcode.com/problems/path-sum-ii/
给定一个二叉树，给定一个int值sum，求二叉树根节点到叶子节点的路径和为sum的所有情况
Example:
Given the below binary tree and sum = 22,
5
/
4 8
/ /
11 13 4
/ \ /
7 2 5 1
Return:
[
[5,4,11,2],
[5,8,4,5]
]

DFS

• 终止条件是 if (val == sum && root.left == null && root.right == null) ，如果用root == null && sum ==0会出现在左右子树遍历两次结果

 public List<List<Integer>> pathSum2(TreeNode root, int sum) {
        List<Integer> out = new ArrayList<Integer>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        pathSum2Helper(root, sum, out, res);
        return res;
    }

    public void pathSum2Helper(TreeNode root, int sum, List<Integer> out, List<List<Integer>> res) {
        if (root == null) {
            return;
        }

        int val = root.val;

        if (val == sum && root.left == null && root.right == null) {
            out.add(val);
            res.add(new ArrayList<Integer>(out));
            out.remove(out.size() - 1);
            return;
        }
        out.add(val);
        pathSum2Helper(root.left, sum - val, out, res);
        pathSum2Helper(root.right, sum - val, out, res);
        out.remove(out.size() - 1);
    }