《剑指offer》 第34题 二叉树中和为某一值的路径

题目描述
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

由于是从根节点开始，并且是找路径，所以是和前序遍历有关。仅仅分析到这里。又是看别人答案的一题...
 首先，选择一种思想，要么是加入一个节点求和，最后判断和是否为target，另一种思想就是加入一个节点就做减法，直到最后减为0。
 以减法为例，当检查一棵树从根到叶子节点形成的路径的和是否为target时，先将当前根节点的值 root.val 加入path, 然后检查它的左子树（若非空），看从左子树的根到叶子节点形成的路径的和是否为 target-root.val (此时调用递归), 然后同样的道理去递归检查右子树（若非空），终止条件是为差值为0，并且也到了树的叶子节点时，才算一次成功的路径。
解法：递归（并没有完成题目中要求的排序）

public class Solution {
  ArrayList<ArrayList<Integer>> res = new ArrayList<>();//res每一个元素都是一条路径
    ArrayList<Integer> path = new ArrayList<>();//path表示某一次的路径
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if (root == null) {
            return res;
        }
        findPath(root, target);
        return res;
    }
    public void findPath(TreeNode root, int target) {
        //进入本次递归前就进行了null的判断，因此不用判断就可以将值加入到path数组中
        path.add(root.val);
        //已经到达叶子节点，并且正好加出了target（3个条件同时满足）
        if (root.val == target && root.left == null && root.right == null) {
//将该路径加入res结果集中
//注意这里不是res.add(path);这是因为ArrayList是引用传递，保持了这一个path，以后如果又成功了
//保持下一个path时，原来保存的path就跟着变成新成功的path了。这个点非常重要！！！！
//所以每一次成功时，都需要建一个新的数组copy一份path,这样以后的path再变的时候，不会影响原来的
//复制的方法是使用构造方法传入，因为Array实现了ICollection方法。所以向数组中传递了一个数组
//我太菜了。。没看懂写的什么意思。用for循环赋值来完成赋值或者数组的copy方法也是可以的。
            res.add(new ArrayList(path));
        }
        //如果左子树非空，递归左子树
        if (root.left != null) {
            findPath(root.left, target - root.val);
        }
        //如果右子树非空，递归右子树
        if (root.right != null) {
            findPath(root.right, target - root.val);
        }
//进入下面两行时，说明完成了某次递归时，条件不满足了，因此需要回溯一次
//因此将最近添加的一个节点（最后一个）去掉，然后返回。
//这里并没有将target-root.val同步更新，是因为这个是方法中的变量，所以返回后，会变成原来那个。
//java某个方法中的变量在调用其他方法，其他方法修改这个变量，返回到原来的方法时，变量不会改变。
        path.remove(path.size() - 1);
        return;
    }
}

总结：本题并没有根据考虑题目中的排序，对我而言，已经有很多坑和注意的点了，通过这个题，也把基础又加强了一点。