Question:

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

Thinking:

We should use classic dfs method to solve this problem and record all the results.

Solution:

But my first version of solution is time limit exceeded:

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<Integer> res = new ArrayList<Integer>();

    return dp(root, sum, res);
}

private List<List<Integer>> dp(TreeNode root, int sum, List<Integer> cur){
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if (root == null)
        return null;
    if (root.left == null && root.right == null){
        if (root.val == sum){
            cur.add(root.val);
            res.add(cur);
            return res;
        }
        else{
            return res;
        }
    }
    for (List<Integer> ele: dp(root.left, sum-root.val, cur)){
        if (ele != null){
            ele.add(0, root.val);
            res.add(ele);
        }
    }
    for (List<Integer> ele: dp(root.right, sum-root.val, cur)){
        if (ele != null){
            ele.add(0, root.val);
            res.add(ele);
        }
    }

    return res;
}

Then I have to improve the effiency of this algorithm, and the code is below:

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<Integer> cur = new ArrayList<Integer>();
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    dp(root, sum, cur, res);

    return res;
}

private void dp(TreeNode root, int sum, List<Integer> cur, List<List<Integer>> res){
    if (root == null)
        return;
    //preorder dfs

    sum -= root.val;
    if (root.left == null && root.right == null){
        if (sum == 0){
            cur.add(root.val);
            List<Integer> tempres = new ArrayList<Integer>();
            tempres.addAll(cur);
            res.add(tempres);
            cur.remove(cur.size() - 1);
        }
        return;
    }
    cur.add(root.val);
    if (root.left != null){
        dp(root.left, sum, cur, res);
    }
    if (root.right != null){
        dp(root.right, sum, cur, res);
    }
    cur.remove(cur.size() - 1);
}

It’s very importatn to create a new List while put the current list data to final result, becuase if not we will only copy the address of this variable cur. Then it will be incorrect if we revise cur.