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

题目

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

思路

回溯法的最佳实践！

注意题的要义是根结点到叶子结点值为和才是路径，所以在这次的题目中不断对树的每一个孩子进行一个新的状态的递归求和，当回溯的时候，就需要进行状态重置，而状态重置在本题中需要进行两次！

• 一次是左子树完事，回溯，状态重置
• 一次是右子树完事，回溯，状态重置

而且分外注意！对于叶子结点要额外处理，叶子结点的左右孩子都为 null，对于一条正确的路径：不能让它回溯两次，因为：

• 第一次状态，到底 null，得到正确答案
• 回溯
• 第二次状态，再次到底 null，又得到正确答案
• 回溯

可以看到回得到两次答案，重复了，所以要判断一下叶子结点的情况，其他非叶子结点就回溯两次

public class Solution {
    private ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
    private Stack<Integer> path = new Stack();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if (root == null) {
            return new ArrayList<>();
        }
        find(root, target, 0);
        return paths;
    }

    private void find(TreeNode root, int target, int cur) {
        if (cur == target && root == null) {
            paths.add(new ArrayList(path));

            return;
        }
        if (root == null) {
            return;
        }

        path.push(root.val);
        find(root.left, target, cur + root.val);
        path.pop();

        if (root.left == null && root.right == null) {
            return;
        }

        path.push(root.val);
        find(root.right, target, cur + root.val);
        path.pop();
    }
}

总结

这次主要是重复值想了好一会，终于靠着慢慢 debug 想出来了发现碰到 null 的重复情况，这其实也跟二叉树遍历有关，这个回溯有点像二叉树的前序遍历，递归的时候，我们可以访问到一个结点三次！