剑指offer----二叉树中和为某一值的路径

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

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/

分析题目：

• 某个路径上的节点的和为输入的数。
• 看到了路径，想到了深度优先遍历，这一定是一道深度优先遍历的题。
• 既然是深度优先遍历，那应该使用栈或者递归。

那么就会产生下面几个问题：

• 如何存储路径上的和的值
• 如果使用递归，终止条件的选择
• 如果发现一个路径与符合题意，如果将其放入ArrayList中
• 多个符合条件的路径公用一些节点

public class Solution {
    private ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();//存储结果
    private ArrayList<Integer> array = new ArrayList<>();//用于存储当前调用栈的节点，递归结束节点自动删去。
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null){
            return arrayLists;//结束
        }
        array.add(root.val);//将本节点的值加入array中
        target -= root.val; //target减去该路径中每层节点的值
        if(target == 0 && root.left == null && root.right == null){//符合题意的条件
            arrayLists.add(new ArrayList<>(array));//将该路径加入到结果中
        }
        FindPath(root.left, target);//左子节点递归
        FindPath(root.right, target);//右子节点递归
        array.remove(array.size() - 1);//从array中移除本层节点，保证array中的永远保存的是执行体所在的节点以上的路径。保证数据清洁，
        return arrayLists;//返回值仅用于最后的返回条件，无时间逻辑意义
    }
}

可以说，这是我刷题以来见过的最棒的一个代码了，从这里面学了很多知识

• 无用的数据及时删除，可以保证整个数据的整洁。
• 当需要记录很多个array时，可以通过构造参数复制公共array，之后公共array仍可以安全的更新