二叉搜索树算法

MrHe··3 min read

啥是二叉搜索树？简单说，它就是一棵有点“规矩”的二叉树。规矩如下：

  1. 对于树中的任意一个节点，它的左子树上所有节点的值，都小于这个节点的值。

  2. 对于树中的任意一个节点，它的右子树上所有节点的值，都大于这个节点的值。

  3. 它的左、右子树也分别为二叉搜索树。

  4. 树中不存在值相等的节点。

这个结构最大的好处就是查找效率高，平均情况下查找、插入、删除的时间复杂度都是 O(log n)，跟二分查找似的。

光说概念没意思，咱们得上题。来看一道最经典也最基础的题目：验证一棵二叉树是否为二叉搜索树。

给你一个二叉树的根节点 root ，判断它是否是一个有效的二叉搜索树。

// 这是我们用到的树节点定义
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;
    }
}

解法一：一拍脑袋，然后掉坑里

刚看到这题，我第一反应通常是：这不就是把定义翻译成代码吗？对于任何一个节点 node，我只要检查 node.left.val < node.val 和 node.val < node.right.val 不就行了？然后对它的左右子树也做同样的事，递归下去。

思路看起来很清晰：

  1. 如果一个节点是空的，那它肯定是一棵合法的BST。

  2. 如果它的左子节点不为空，并且左子节点的值大于等于当前节点的值，那肯定不行。

  3. 如果它的右子节点不为空，并且右子节点的值小于等于当前节点的值，那也肯定不行。

  4. 上面都通过了，再递归地去检查它的左子树和右子树是不是BST。

代码写出来大概长这样：

public boolean isValidBST_V1(TreeNode root) {
    if (root == null) {
        return true;
    }
    // 只检查了直接的父子关系
    if (root.left != null && root.left.val >= root.val) {
        return false;
    }
    if (root.right != null && root.right.val <= root.val) {
        return false;
    }
    // 递归检查左右子树
    return isValidBST_V1(root.left) && isValidBST_V1(root.right);
}

这代码看起来是不是挺完美的？来，我们跑个测试用例：

    5
   / \
  1   7
     / \
    6   8

用上面的代码跑一下：

  • 节点5：1 < 5，5 < 7，OK。

  • 节点1：左右子树为空，OK。

  • 节点7：6 < 7，7 < 8，OK。

  • ...

所有节点都通过了检查，代码会返回 true。但这棵树是合法的BST吗？当然不是！ 问题出在节点 6 上。虽然 6 作为 7 的左孩子是合法的 (6 < 7)，但它在 5 的右子树里，按照定义，5 的右子树所有节点都应该大于 5，而 6 并不大于 5。

坑在哪里？ 我们只顾着比较父子节点，忽略了BST定义的全局性。一个节点的值不仅要和它的父节点比较，还要和它所有的祖先节点比较。节点 6 的值，不仅要小于 7，还要大于 5。

这个解法看似直观，却是最典型的错误。面试时如果你先写出这个，然后自己找到问题并改进，反而会成为加分项。

解法二：递归的真正用法 —— 带着约束往下走

既然知道了问题在于全局约束，那我们递归的时候就不能只传一个节点信息，还得把约束条件带下去。这个约束是什么？就是一个值的范围 (min, max)。

对于树中的每一个节点，它的值都必须在这个 (min, max) 的开区间内。

  • 最开始，对于根节点，它没啥约束，值可以是任何数。我们可以认为它的范围是 (负无穷, 正无穷)。

  • 当我们从当前节点 node 往下走到它的左子节点 node.left 时，node.left 的值必须满足什么条件？它必须小于 node.val。所以，对于左子树来说，它们的值上限变成了 node.val，下限不变。新的范围就是 (min, node.val)。

  • 同理，当我们往下走到右子节点 node.right 时，node.right 的值必须大于 node.val。所以，对于右子树来说，它们的值下限变成了 node.val，上限不变。新的范围就是 (node.val, max)。

这个思路就把全局的约束条件，通过递归参数，一级一级地传递下去了。

代码实现：

public boolean isValidBST_V2(TreeNode root) {
    // 根节点的范围是 (null, null)，我们用 null 表示无穷
    return isValid(root, null, null);
}

// 辅助函数，带着值的上下界进行递归
private boolean isValid(TreeNode node, Integer lower, Integer upper) {
    if (node == null) {
        return true;
    }

    // 检查当前节点的值是否在合法范围内
    // 如果有下界，且当前值不大于下界，非法
    if (lower != null && node.val <= lower) {
        return false;
    }
    // 如果有上界，且当前值不小于上界，非法
    if (upper != null && node.val >= upper) {
        return false;
    }

    // 递归检查左子树，更新上界为当前节点的值
    // 递归检查右子树，更新下界为当前节点的值
    // 必须两边都合法才行
    return isValid(node.left, lower, node.val) && isValid(node.right, node.val, upper);
}

小提示：在实际编码中，用 Integer 类型作为边界 lower 和 upper 很方便，因为 null 可以完美地代表无穷大或无穷小。如果树中可能包含 Integer.MIN_VALUE 或 Integer.MAX_VALUE，为了避免边界判断的麻烦，可以直接用 Long 类型的 (Long.MIN_VALUE, Long.MAX_VALUE) 作为初始范围。

这个解法，思路清晰，正确性也得到了保证，是解决这类问题的标准递归范式。

解法三：换个角度看问题 —— 中序遍历的魔法

除了硬核地递归检查，我们还能不能从BST的特性本身找点灵感？

BST有一个非常、非常、非常重要的性质：BST的中序遍历结果是一个严格递增的序列。

为什么？中序遍历的顺序是“左-根-右”。根据BST的定义（左 < 根 < 右），这个遍历顺序天然就会把节点从小到大排好序。

有了这个性质，问题就转化成了：

  1. 对给定的二叉树进行中序遍历。

  2. 判断遍历得到的结果序列是否是严格递增的。

实现方式1：存到列表里再判断

最直接的办法，就是把中序遍历的结果存到一个 ArrayList 里，然后遍历这个 ArrayList，看看是不是后一个元素都比前一个大。

public boolean isValidBST_V3_A(TreeNode root) {
    List<Integer> inorderList = new ArrayList<>();
    inorderTraversal(root, inorderList);

    // 检查列表是否严格递增
    for (int i = 0; i < inorderList.size() - 1; i++) {
        if (inorderList.get(i) >= inorderList.get(i + 1)) {
            return false;
        }
    }
    return true;
}

private void inorderTraversal(TreeNode node, List<Integer> list) {
    if (node == null) {
        return;
    }
    inorderTraversal(node.left, list);
    list.add(node.val);
    inorderTraversal(node.right, list);
}

这个方法虽然简单粗暴，但缺点是需要 O(N) 的额外空间来存储遍历结果。对于一棵很大的树，这可能会成为问题。

实现方式2：边遍历边判断（空间优化）

我们真的需要把所有节点都存起来吗？其实没必要。在进行中序遍历时，我们只需要比较当前节点和中序遍历中的上一个节点的值就行了。如果当前节点的值小于等于上一个节点的值，那就直接返回 false。

这个“上一个节点的值”怎么记录？我们可以用一个全局变量或者一个包装类来传递。

// 使用一个变量记录前驱节点的值
// 用 long 类型是为了处理 root.val = Integer.MIN_VALUE 的边界情况
private long prev = Long.MIN_VALUE; 

public boolean isValidBST_V3_B(TreeNode root) {
    if (root == null) {
        return true;
    }

    // 1. 访问左子树
    if (!isValidBST_V3_B(root.left)) {
        return false;
    }

    // 2. 访问当前节点
    // 如果当前节点的值不大于前一个节点的值，说明不是递增的
    if (root.val <= prev) {
        return false;
    }
    // 更新 prev 为当前节点的值
    prev = root.val;

    // 3. 访问右子树
    return isValidBST_V3_B(root.right);
}

这个解法非常巧妙，它把中序遍历和大小判断融合在了一起，空间复杂度降到了 O(H)（H是树的高度，即递归栈的深度），在思路上也是一个不小的提升。

总结一下思路

今天我们从一个简单的验证BST的问题，看到了三种不同的解题思路：

  1. 直觉但错误的解法：只考虑局部父子关系，这是思考树问题时最容易犯的错误。它提醒我们，树的属性往往是全局的，不能只看眼前。

  2. 带约束的递归：通过递归函数的参数，将全局的约束（值的上下界）传递下去。这是解决树相关问题的一个通用且强大的范式，必须掌握。

  3. 利用数据结构性质：抓住BST中序遍历是递增序列这一核心特性，将问题巧妙地转化为序列判断问题。这种“换个赛道”的思路，往往能让复杂问题变得简单。

  • #5lqm5yj5pcc57si5qcr