剑指-24----递归解法---java

我直接上代码，具体说明都在代码的注释当中。

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> listAll=new ArrayList<>();
        ArrayList<Integer> list =new ArrayList<>();
        Method(listAll,list,root,target);
        return listAll;

    }
    public void Method(ArrayList<ArrayList<Integer>> listAll,ArrayList<Integer> list,TreeNode root,int target){
        if(root==null){return;}
        list.add(root.val);
        target-=root.val;
        //当有子树时，对当前已有的list进行复制。这样当到达叶子结点时，list里会有之前的路径，如果加起来不等于target，那么直接扔掉不管就行。
        //如果等于，加到listAll中。
        if(root.left!=null){
            ArrayList<Integer> newList=new ArrayList<Integer>(list);
            Method(listAll,newList,root.left,target);
        }
        if(root.right!=null){
            //为了更好地理解，我在这copy出一个新的list，其实更好地做法是一个用的新的复制的list，一个对之前的list进行操作，这样节省空间。
            //ArrayList<Integer> newList=new ArrayList<Integer>(list);
            //Method(listAll,newList,root.right,target);
            Method(listAll,list,root.right,target);

        }
        //if(target == 0 && root.left == null && root.right == null){
        //    listAll.add(new ArrayList<Integer>(list));
        //}
            //这里必须new一个新的空间来存放list，否则listAll中存放list地址引用，会在下一行remove操作时改变已经存放进listAll中的list中的值 
        //list.remove(list.size()-1);


        //当左子树使用新list时，不管右子树是否使用新list，递归完左子树时不用list.remove(list.size()-1)
        //同时意味着向listAll中添加时可以直接添加list而不用new个新的出来。
        //因为左子树和右子树用的不是一个list，这对整个树来说都是一样的。
        //如果左右子树的递归都用的是list而不是newList,那么就需要进行remove操作。
        if(target == 0 && root.left == null && root.right == null){
            listAll.add(list);
        }
    }
}