import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>> ();
ArrayList<Integer> temp = new ArrayList<Integer>();
recursion(root,sum,temp,result);
return result;
}
public void recursion(TreeNode root, int sum, ArrayList<Integer> temp, ArrayList<ArrayList<Integer>> result){
if(root == null) return;
if( sum == root.val && root.left == null && root.right == null){
temp.add(root.val);
result.add(temp);}
else{
ArrayList<Integer> left = new ArrayList<Integer>();//use an arraylist to store value
left.addAll(temp);//previous value
left.add(root.val);
ArrayList<Integer> right = new ArrayList<Integer>();
right.addAll(temp);
right.add(root.val);
recursion(root.left,sum - root.val,left,result);
recursion(root.right,sum - root.val,right,result);
}
}
}