Binary Tree Recursive Solution - Path Sum II

1. Clone the list to separate the reference
2. Remove last node added for next iteration
3. Recursive with the advantage of pass by reference in Java


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> l =new ArrayList<Integer>();
        dfs(root, sum, list, l);
        return list;
    }
   
    private void dfs(TreeNode root, int sum, ArrayList<ArrayList<Integer>> list, ArrayList<Integer> l){
        if(root == null){
            return;
        }
   
 
        if(root.val==sum && root.left==null && root.right==null){
            l.add(root.val);
           
         
            ArrayList<Integer> clone = new ArrayList<Integer>(l);
            list.add(clone);
           
            l.remove(l.size()-1);     //update l since l is linked to the reference… for all other solutions.
            return;
        }
   
        l.add(root.val);
        dfs(root.left, sum-root.val, list, l);
        dfs(root.right, sum-root.val, list, l);
        l.remove(l.size()-1);    
    }
}