54. Path Sum II

/**
 * 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>> res = new ArrayList<ArrayList<Integer>> ();
       
        if (root==null) return res;
       
        ArrayList<Integer> temp = new ArrayList<Integer> ();
       
        getlist(root, sum, res, temp);
        return res;
    }
   
    public void getlist(TreeNode root, int sum, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> temp) {
        if (root==null) return;
       
        if (root.left==null && root.right==null && sum-root.val==0) {
            temp.add(root.val);
            res.add((ArrayList<Integer>) temp.clone());
            temp.remove(temp.size()-1);
            return;
        }
       
        temp.add(root.val);
        getlist(root.left, sum-root.val, res, temp);
        getlist(root.right, sum-root.val, res, temp);
        temp.remove(temp.size()-1);
    }
}