Question

link

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

Stats

Frequency 2
Difficulty 2
Adjusted Difficulty 3
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a standard question

Solution

My code is simple DFS. However, the coding part is not easy. Note that value can be negative, and think about when to add result into list.

Just write it by hand and get an idea of it.

Code

public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    helper(root, sum, new ArrayList<Integer>(), ans);
    return ans;
}

private void helper(TreeNode node, int total, ArrayList<Integer> list,
                    ArrayList<ArrayList<Integer>> ans) {
    if (node == null) return;
    list.add(node.val);
    if (node.val == total && node.left == null && node.right == null)
        ans.add(new ArrayList(list));
    helper(node.left, total - node.val, list, ans);
    helper(node.right, total - node.val, list, ans);
    list.remove(list.size() - 1);
}