二叉树 DFS、回溯与几道经典题的写法

一、搜索和遍历

BFS 和 DFS 都是搜索的基础套路。它们常常出现在图和树里，写法上是遍历，目的上是找答案，所以很多时候也没必要把'遍历'和'搜索'分得太死。

BFS 是一层一层往外扩，先看离起点近的节点；DFS 则是沿着一条路尽量往深处走，走不动了再回头换路。前者更像按圈找，后者更像顺着岔路一路摸到底。

暴力搜索也离不开这两种思路。说白了，就是把所有情况都试一遍，靠枚举拿结果。题目规模小、没有明显优化空间时，这种办法很直接；代价也很明显，数据一大就容易跑不动。

二、回溯其实就是带剪枝的 DFS

回溯和 DFS 的关系没必要绕弯子，本质上就是 DFS。区别在于，回溯会更强调'试一下、走不通就退回来'，然后继续尝试别的分支。

迷宫题很适合拿来理解这件事。沿着一条路往下走，走到死胡同时撤回上一个岔口，再换另一条路。提前知道某条路不可能得到答案时，直接丢掉，这一步就是剪枝。这个思路在题里用得非常多，尤其是搜索空间一大时，剪枝基本决定了能不能过。

三、几道典型题

3.1 计算布尔二叉树的值

这题的树是完整二叉树：要么没有节点，要么左右孩子都在。叶子节点存布尔值，非叶子节点存逻辑与或逻辑或。题目真正要做的事，就是把整棵树从下往上算出来。

我一般会把它看成后序遍历。先拿到左右子树的结果，再回到当前节点做合并。叶子节点是递归出口，直接返回当前值，不需要再往下看。代码也就顺着这个思路写，结构很短。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val; this.left = left; this.right = right;
 *   }
 * }
 */
class Solution {
    public boolean evaluateTree(TreeNode root) {
        if (root.left == null) {
            return root.val == 1;
        }
        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val == 2 ? (left || right) : (left && right);
    }
}

3.2 求根节点到叶节点数字之和

这题要求把每条根到叶子的路径当成一个数字，最后把所有数字加起来。路径上的值要一路向下拼接，到了叶子节点再结算。

这里递归参数里带一个 preSum 会比较顺手。每往下一层，就把当前节点接到数字后面；走到叶子时直接返回这个路径值。这样不用额外维护路径字符串，逻辑也更紧凑。代码里那种'先乘 10，再加当前值'的写法，基本就是这类题的标准处理方式。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val; this.left = left; this.right = right;
 *   }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int preSum) {
        preSum = preSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return preSum;
        }
        int ret = 0;
        if (root.left != null) ret += dfs(root.left, preSum);
        if (root.right != null) ret += dfs(root.right, preSum);
        return ret;
    }
}

3.3 二叉树剪枝

题意很直接：删掉所有不包含 1 的子树。也就是说，一个节点如果最后只剩下自己，而且值还是 0，它就没必要留着。

这类题还是得用后序遍历。原因很简单，想知道当前节点能不能删，必须先知道左右子树有没有留下东西。先递归处理左右孩子，再回到当前节点判断是不是'空且为 0'，是的话返回 null。把返回值接回父节点，剪枝就完成了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val; this.left = left; this.right = right;
 *   }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0) {
            return null;
        }
        return root;
    }
}

3.4 验证二叉搜索树

二叉搜索树最顺手的判断方式，就是中序遍历。因为它遍历出来天然是递增序列，只要当前节点值比前一个节点大，整棵树就继续成立；一旦不满足，后面也不用看了。

这里用一个 prev 记录前一个访问到的值会比较省事。递归到当前节点时，先去看左子树，左边不合法就直接返回。然后比较当前值和 prev，更新 prev，最后再递归右子树。题里其实没有什么花活，关键是尽早停，不要傻乎乎把整棵树都扫完。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val; this.left = left; this.right = right;
 *   }
 * }
 */
class Solution {
    long prev = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        boolean left = isValidBST(root.left);
        // 剪枝
        if (left == false) return false;
        boolean cur = false;
        if (root.val > prev) cur = true;
        prev = root.val;
        boolean right = isValidBST(root.right);
        return left && cur && right;
    }
}

3.5 二叉搜索树中第 K 小的元素

这题和上一题很像，还是靠中序遍历。不同的是，这里要找的是第 k 个节点，所以再加一个计数器就够了。

遍历到一个节点就让 count--，当 count == 0 时，当前节点就是答案，直接记录下来并停止继续搜索。这个地方的剪枝很有用，没必要把后面的节点也走完。代码里保留两个全局变量，一个记数，一个存结果，思路清楚，写起来也干净。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val; this.left = left; this.right = right;
 *   }
 * }
 */
class Solution {
    int count;
    int ret;

    public int kthSmallest(TreeNode root, int k) {
        count = k;
        InOrder(root);
        return ret;
    }

    public void InOrder(TreeNode root) {
        if (root == null || count == 0) return;
        InOrder(root.left);
        count--;
        if (count == 0) ret = root.val;
        if (count == 0) return;
        InOrder(root.right);
    }
}

3.6 二叉树的所有路径

这题要输出所有从根到叶子的路径，格式是字符串，中间用 -> 连起来。

写回溯时，路径字符串最容易出问题的地方就是'恢复现场'。你如果把同一个字符串对象一路往下改，回来的时候就很容易串掉。所以我更倾向于把当前路径作为参数传下去，每一层自己拷贝一份，再追加当前节点值。叶子节点直接把路径放进结果集，不是叶子就补上 -> 再继续往下走。处理到左子树为空、右子树不为空的情况时，正常继续递归就行，没必要额外绕一层判断。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val; this.left = left; this.right = right;
 *   }
 * }
 */
class Solution {
    List<String> ret;

    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList<>();
        DFS(root, new StringBuffer());
        return ret;
    }

    public void DFS(TreeNode root, StringBuffer _path) {
        StringBuffer path = new StringBuffer(_path);
        path.append(Integer.toString(root.val));
        if (root.left == null && root.right == null) {
            ret.add(path.toString());
            return;
        }
        path.append("->");
        if (root.left != null) DFS(root.left, path);
        if (root.right != null) DFS(root.right, path);
    }
}