113.Path Sum II

Posted on | In

Solution 1: accepted 2ms

  1. Need to reset the condition of ArrayList using temp.remove(temp.size() - 1).
  2. Why result.add(new ArrayList<Integer>(temp)) ? It passes a reference rather than an object. So if we use result.add(temp), we will get the same temp multiple times. In addition, temp will contains no elements at the end of the recursion, so we will always get a list of [] at the end.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
        dfs(root, sum, result, temp);
        return result;
    }
    
    private void dfs(TreeNode root, int sum, List<List<Integer>> result, List<Integer> temp) {
        if (root == null) return;
        
        temp.add(root.val);
        
        if (root.left == null && root.right == null && sum == root.val) {
            result.add(new ArrayList<Integer>(temp)); // Why?
        } else {
            dfs(root.left, sum - root.val, result, temp);
            dfs(root.right, sum - root.val, result, temp);
        }
        temp.remove(temp.size() - 1);
    }
}

Alternative 

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
public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
        dfs(root, sum, result, temp);
        return result;
    }
    
    public void dfs(TreeNode root, int sum, List<List<Integer>> result, List<Integer> temp) {
        if (root == null) return;
        temp.add(root.val);
        if (sum - root.val == 0 && root.left == null && root.right == null) {
            result.add(temp);   
            return;        
        } 
        if (root.left != null) {
            dfs(root.left, sum - root.val, result, temp);
            temp.remove(temp.size() - 1);
        }
        if (root.right != null) {
            dfs(root.right, sum - root.val, result, temp);
            temp.remove(temp.size() - 1);
        }
    }
}