Question

link

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

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

Stats

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);
}