[LeetCode] 113. Path Sum II

Posted on | In

Problem

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

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

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

Return:

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

Explanation

  1. We can use recusive backtracking to solve this, so we create a helper function and pass a temp list and result list as the parameters besides the root node and sum.

  2. Inside the helper function, the base case is if the root node is NULL, we just return nothing. Then, we add the current root node’s value to the temp list.

  3. Then we check if the current node’s value equal to the sum and also there’s no left and right node, then we add temp list to the result list.

  4. Next, we recrusively call the helper function with the left and right child nodes with the updated sum=sum-root.val. Then, we should remove the last element of the temp list in order to backtract to the parent node.

Solution

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    void helper(TreeNode root, int sum, List<Integer> lst, List<List<Integer>> res) {
        if (root == null) return;
        lst.add(root.val);
        if (root.val == sum && root.left == null && root.right == null) {
            res.add(new ArrayList<>(lst));
            // lst.remove(lst.size()-1);
            // return;
        }
        helper(root.left, sum-root.val, lst, res);
        helper(root.right, sum-root.val, lst, res);
        lst.remove(lst.size()-1);
    }
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) return res;
        List<Integer> lst = new ArrayList<>();
        helper(root, sum, lst, res);
        return res;
    }
}