//方案一:

public class Solution {

ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

ArrayList<Integer> temp = new ArrayList<Integer>();


public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {

    if(root==null)
        return list;
    f(root,target,0);
    return list;
}

public  void f(TreeNode root, int target,int sum){
    if(root==null)
        return;
    
    sum=root.val + sum;
    
    if(root.left==null&&root.right==null){
        if(sum==target)
        {
            temp.add(root.val);
            ArrayList<Integer> temp1 = new ArrayList<Integer>(temp);
            list.add(temp1);
            temp.remove(temp.size()-1);
        }
      return;
    }
    
    temp.add(root.val);
    f(root.left,target,sum);
    f(root.right,target,sum);
    temp.remove(temp.size()-1);
    
}

}

//方案二:

public class Solution {

ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

ArrayList<Integer> temp = new ArrayList<Integer>();


public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
    if(root==null)
        return list;
    f(root,target,0);
    return list;
}

public  void f(TreeNode root, int target,int sum){
    if(root==null)
        return;
    
    sum=root.val + sum;
    
    if(sum==target){
        if(root.left==null&&root.right==null)
        {
            temp.add(root.val);
            ArrayList<Integer> temp1 = new ArrayList<Integer>(temp);
            list.add(temp1);
            temp.remove(temp.size()-1);
        }
      return;
    }
	//可以从这个地方优化
	else if(sum>target)
        return;
        
    temp.add(root.val);
    //也可以从这个地方优化
    if(root.left!=null&&((sum+root.left.val)<=target))
    f(root.left,target,sum);
    if(root.right!=null&&((sum+root.right.val)<=target))
    f(root.right,target,sum);
    temp.remove(temp.size()-1);
    
}

}

方案二为方案一的优化:去掉不必要的递归

12-03 09:56