二叉树中和为某一值的路径(LeetCode Offer 34)

题目

找到二叉树中节点值的和为输入整数的所有路径。
注：从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

解析

回溯递归方法。假如输入的整数为sum，对于某一个节点，sum减去这个结点的值得到另外一个整数，这个得到的整数相对于这个结点的左右子树又是一个新的二叉树寻找和为指定整数的路径问题。所以这是一个典型的递归问题。不过，在递归的过程中，需要对结果进行回溯，因为记录路径的数据结构，当遍历完当前节点之后需要回退到上一步的状态，继续进行上一级其他节点的递归调用。

代码

class PathSum {
    //保存找到的路径
    private List<List<Integer>> list = new LinkedList<>();
     //递归回溯时记录走过的节点，使用LinkedList结构，模拟栈进行回溯
    private LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        //递归边界条件
        if(null == root){
            return list;
        }
        //当前节点放入记录的队列中
        path.add(root.val);
        //递归边界条件
        //如果已经是叶子节点，并且结果等于递归传入的sum，则找到一条路径
        if(root.val == sum && root.left == null && root.right == null){
            LinkedList<Integer> nl = new LinkedList<>();
            nl.addAll(path);
            list.add(nl);
        }
        //递归查找当前节点的左右子树
        pathSum(root.left, sum - root.val);
        pathSum(root.right, sum - root.val);
        //左右子树递归结束后，进行回溯，到当前节点之前的状态
        path.removeLast();
        return list;
    }
}