24二叉树中和为某一值的路径

题目描述

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

public class Solution {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> curpath =  new ArrayList<Integer>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
         pa( root,target,0);
        return result;
    }
    public void pa(TreeNode root,int target,int sum){
       
        if(root==null) 
            return ;              
        curpath.add(root.val);
        sum+=root.val;    
        if(root.left==null && root.right == null){
            if(target == sum ){
                ArrayList path = new ArrayList<Integer>(curpath);
                result.add(path);             
            }
            curpath.remove(curpath.size()-1);
            sum-=root.val;
            return;
        } 
            pa(root.left,target,sum);
            pa(root.right,target,sum);
            curpath.remove(curpath.size()-1);
            sum-=root.val;

    }
}

20180308

 1 import java.util.ArrayList;
 2 /**
 3 public class TreeNode {
 4     int val = 0;
 5     TreeNode left = null;
 6     TreeNode right = null;
 7 
 8     public TreeNode(int val) {
 9         this.val = val;
10 
11     }
12 
13 }
14 */
15 public class Solution {
16     ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
17     ArrayList<Integer> restemp = new ArrayList<Integer>(); 
18     public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
19         if(root==null) return res;
20         target = target - root.val;
21         restemp.add(root.val);
22         if(target==0&&root.left==null&&root.right==null){
23             res.add(new ArrayList<Integer>(restemp));
24         }
25         FindPath(root.left,target);
26         FindPath(root.right,target);
27         restemp.remove(restemp.size()-1);
28         return res;
29 
30     }
31 }