113. Path Sum II (Medium) Bloomberg

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For 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]
]

Solution 1: DFS O(n); O(h)

    /**
     * Solution1: DFS O(n); O(h)
     * Subtract the value of current node from sum until it reaches a leaf node.
     * If current sum equals 0, add current path to result.
     */
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, new ArrayList<>(), root, sum);
        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> path, TreeNode root, int sum) {
        if (root == null) {
            return;
        }

        sum -= root.val; //先减然后和0比较。
        path.add(root.val); 
        if (root.left == null && root.right == null && sum == 0) {
            res.add(new ArrayList<>(path)); //注意深拷贝，很久不写DFS就会忘记。
        }

        dfs(res, path, root.left, sum);
        dfs(res, path, root.right, sum);
        path.remove(path.size() - 1);
    }

另一种写法

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        dfs(res, new ArrayList<>(), root, sum);
        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> temp, TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        temp.add(root.val);
        if (root.left == null && root.right == null && root.val == sum) {
            res.add(new ArrayList<>(temp));
        }
        dfs(res, temp, root.left, sum - root.val);
        dfs(res, temp, root.right, sum - root.val);
        temp.remove(temp.size() - 1);
    }