二叉树中和为某一值的路径 FindPath<TODO输入一个二叉树>

 1 import java.util.ArrayList;
 2 /**
 3 public class TreeNode {
 4     int val = 0;
 5     TreeNode left = null;
 6     TreeNode right = null;
 7     public TreeNode(int val) {
 8         this.val = val;
 9     }
10 }
11 */
12 public class Solution {
13     //这两个初始化要放在FindPath函数的外面
14     //因为后期要不停地调用函数,两个声明不能多次地被声明
15     ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
16     ArrayList<Integer> list = new ArrayList<Integer>();
17     public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
18         //考虑特殊情况
19         if(root== null)    return result;
20         list.add(root.val);
21         target -= root.val;    //从求和间接变成了减法,这个思想很多地方都会用的到
22         //做完减法后,如果target<0,就没有必要继续遍历树了
23         //比如说root是10,target是3,此处加个判定会更合适一些
24         if(target>=0){
25             //走到target==0这一步,说明一条成功的路径已经找到,加到最终结果result中去
26             if(target==0 && root.left == null && root.right==null){
27                 //这步操作吊炸天,不重新new的话从始至终result中所有引用都指向了同一个一个list
28                 result.add(new ArrayList<Integer>(list));
29             }
30             if(root.left!=null)  FindPath(root.left,target);
31             if(root.right!=null) FindPath(root.right,target);
32             //递归到叶子节点如果还没有找到路径，就要回退到父节点继续寻找,移除不成功的路径的节点是有必要的
33             list.remove(list.size()-1);
34         }
35         return result;
36     }
37 }

 1 public class Solution {
 2     ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 3     ArrayList<Integer> list = new ArrayList<Integer>();
 4     public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
 5         if(root== null)    return result;
 6         list.add(root.val);
 7         target -= root.val;   
 8         if(target>=0){
 9             if(target==0 && root.left == null && root.right==null){
10                 result.add(new ArrayList<Integer>(list));
11             }
12             if(root.left!=null)  FindPath(root.left,target);
13             if(root.right!=null) FindPath(root.right,target);
14             list.remove(list.size()-1);
15         }
16         return result;
17     }
18 }