/ Data Structure and Algorithms  

Leetcode 113. Path Sum II

Question



Given a sum, output tha paths which starts from the root node to the leaf nodes, and add up to sum.

Similar Question

Solution

This is an upgrade version from 112. Path Sum. For that question, we have the solution as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) {
        return false;
    }

    // reach leave node
    if (root.left == null && root.right == null && sum == root.val) {
        return true;
    }

    // check left tree and right tree
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

Here we need an ans variable to hold all the results. A temp variable to hold the traversed path. The thing to note is that the list in java is passed by reference, so after the recursion, you must delete the previously added elements without affecting the temp of other branches.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> results = new ArrayList<>();

    if (root == null) {
        return results;
    }

    sum(root, sum, new ArrayList<>(), results);

    return results;
}

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

    // reach leaf node
    if (root.left == null && root.right == null) {
        if (sum == root.val) {
            temp.add(root.val);

            results.add(new ArrayList<>(temp));

            temp.remove(temp.size() - 1);
        }

        return;
    }

    // check left tree
    temp.add(root.val);
    sum(root.left, sum - root.val, temp, results);
    temp.remove(temp.size() - 1);

    // check right tree
    temp.add(root.val);
    sum(root.right, sum - root.val, temp, results);
    temp.remove(temp.size() - 1);
}