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

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

1.思路：
递归算法三部曲：
1).明白递归函数的功能：FindPath(TreeNode* root,int sum)，从root节点出发，找和为sum的路径
2).递归终止条件：当root节点为叶子节点(root.left!=null&&root.right!=null)并且sum==target, 表示找到了一条符合条件的路径
3).下一次递归：如果左子树不空，递归左子树FindPath(root.left, target-root.val),如果右子树不空，递归右子树FindPath(root.right,target-root.val)

public class Solution {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();//全局变量保存返回路径
        ArrayList<Integer> path=new ArrayList<>();//保存每一条满足条件的路径
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root==null){//判空
            return res;
        }
        path.add(root.val);
        target-=root.val;//每一次加入都减一下，直到为0则满足条件
        if(target==0&&root.left==null&&root.right==null){
            //将该路径加入res结果集中
//注意这里不是res.add(path);这是因为ArrayList是引用传递，保持了这一个path，以后如果又成功了
//保持下一个path时，原来保存的path就跟着变成新成功的path了。这个点非常重要！！！！
//所以每一次成功时，都需要建一个新的数组copy一份path,这样以后的path再变的时候，不会影响原来的
//复制的方法是使用构造方法传入，因为Array实现了ICollection方法。所以向数组中传递了一个数组
                res.add(new ArrayList<Integer>(path));//!!!每次重新在堆内存中开辟一个新的空间
        }
          if(root.left!=null) FindPath(root.left,target);
          if(root.right!=null) FindPath(root.right,target);
        //进入下面两行时，说明完成了某次递归时，条件不满足了，因此需要回溯一次
        //因此将最近添加的一个节点（最后一个）去掉，然后返回。
        //这里并没有将target-root.val同步更新，是因为这个是方法中的变量，所以返回后，会变成原来那个。
        //java某个方法中的变量在调用其他方法，其他方法修改这个变量，返回到原来的方法时，变量不会改变。
          path.remove(path.size()-1);//将之前存储的不满足的删除掉
        return res;
    }
}