跳至主要內容

验证二叉搜索树——中序遍历的隐式有序性

老张2026/4/30大约 7 分钟

验证二叉搜索树——中序遍历的隐式有序性

适读人群：Java 后端工程师、准备算法面试的同学 | 阅读时长：约18分钟 | 难度：Medium

开篇故事

98 题是一道经典的 BST 题目，但有一个非常著名的坑——几乎每个初次做这道题的人都会踩。

BST 的性质是"左子节点 < 父节点 < 右子节点"，但这只是局部性质。很多人写出这样的代码：

if (root.left != null && root.left.val >= root.val) return false;
if (root.right != null && root.right.val <= root.val) return false;
return isValidBST(root.left) && isValidBST(root.right);

这个代码会在以下用例失败：

    10
   /  \
  5    15
      /  \
     6    20

节点 6 比根节点 10 小，但它在右子树里，不合法。但上面的代码只检查了"6 < 15（它的父节点）"，没有检查"6 > 10（它的祖先）"。

正确的 BST 验证需要考虑每个节点的合法范围，而不只是与直接父节点的比较。

这篇文章把三种解法都讲清楚，重点在"上下界传递"和"中序遍历隐式有序性"两种思路。

一、题目解析

题目：LeetCode 98. 验证二叉搜索树

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

有效二叉搜索树定义如下：

  • 节点的左子树只包含小于当前节点的数
  • 节点的右子节点的值仅包含大于当前节点的数
  • 所有左子树和右子树自身必须也是二叉搜索树

示例：

输入：root = [2,1,3]
输出：true

输入：root = [5,1,4,null,null,3,6]
输出：false（根节点为5，但右子节点4比5小，不合法）

输入：root = [10,5,15,null,null,6,20]
输出：false（6在15的左子树，满足6<15，但6在10的右子树，不满足6>10）

二、解法一：暴力解法——错误写法示例（教学用）

下面先展示那个著名的错误写法，然后修正：

// 错误写法：只检查父子关系，不检查祖先约束
class WrongSolution {
    public boolean isValidBST(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(root.left) && isValidBST(root.right);
    }
}

正确暴力做法：中序遍历，收集序列，检查是否严格递增。

class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> inorder = new ArrayList<>();
        collectInorder(root, inorder);
        
        for (int i = 1; i < inorder.size(); i++) {
            if (inorder.get(i) <= inorder.get(i - 1)) return false;
        }
        return true;
    }
    
    private void collectInorder(TreeNode node, List<Integer> list) {
        if (node == null) return;
        collectInorder(node.left, list);
        list.add(node.val);
        collectInorder(node.right, list);
    }
}

复杂度分析

  • 时间复杂度：O(n)。中序遍历 O(n)，线性检查 O(n)。
  • 空间复杂度：O(n)。存储中序序列 O(n)，递归栈 O(n)。

三、解法二：上下界传递（DFS 参数传递合法范围）

思路

对每个节点维护它的合法范围 [min, max]：

  • 根节点范围：(-∞, +∞)
  • 左子节点范围：(-∞, 当前节点值)
  • 右子节点范围：(当前节点值, +∞)

递归时把范围传下去，每个节点检查自己是否在合法范围内。

完整代码

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean validate(TreeNode node, long minVal, long maxVal) {
        if (node == null) return true;
        
        // 当前节点值必须在 (minVal, maxVal) 范围内（严格不等）
        if (node.val <= minVal || node.val >= maxVal) return false;
        
        // 左子树：所有节点必须 < node.val
        // 右子树：所有节点必须 > node.val
        return validate(node.left, minVal, node.val)
            && validate(node.right, node.val, maxVal);
    }
}

为什么用 long 而不是 int？

题目中节点值可以是 Integer.MIN_VALUE。如果用 int，初始范围下界 Integer.MIN_VALUE 和节点值 Integer.MIN_VALUE 相等，node.val <= minVal 为 true，会错误地返回 false。用 long 类型避免了这个整数边界问题。

复杂度分析

  • 时间复杂度：O(n)。每个节点访问一次。
  • 空间复杂度：O(n)。递归栈深度为树高，最坏 O(n)。

四、解法三：最优解法——中序遍历隐式检查

思路

BST 的中序遍历结果是严格递增的序列，这是 BST 的一个等价特征。

所以验证 BST 等价于验证其中序遍历是否严格递增。利用这一点，可以在中序遍历的过程中，边遍历边检查，不需要存储完整序列，只需要记住上一个访问的节点值。

Mermaid 图——中序遍历与 BST 有序性

完整代码（递归版）

class Solution {
    private long prev = Long.MIN_VALUE;  // 记录上一个中序访问的节点值
    
    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }
    
    private boolean inorder(TreeNode node) {
        if (node == null) return true;
        
        // 先处理左子树
        if (!inorder(node.left)) return false;
        
        // 检查当前节点是否比上一个访问的节点大
        if (node.val <= prev) return false;
        prev = node.val;
        
        // 再处理右子树
        return inorder(node.right);
    }
}

完整代码（迭代中序版）

class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        long prev = Long.MIN_VALUE;
        TreeNode curr = root;
        
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            
            // 检查当前节点值是否比前一个大
            if (curr.val <= prev) return false;
            prev = curr.val;
            
            curr = curr.right;
        }
        
        return true;
    }
}

复杂度分析

  • 时间复杂度：O(n)。每个节点访问一次。
  • 空间复杂度：O(n)。递归栈或显式栈。
  • 优化点： 发现不合法时提前返回 false，不需要遍历完整棵树。

提交结果：时间击败约 100% 用户，空间击败约 80% 用户。

五、举一反三

同类题目

LeetCode 230. 二叉搜索树中第 K 小的元素 BST 中序遍历的第 k 个元素，直接利用有序性。

LeetCode 501. 二叉搜索树中的众数 中序遍历，找出现次数最多的值。

LeetCode 700. 二叉搜索树中的搜索 利用 BST 的有序性，根据大小关系决定往左还是往右走。

LeetCode 235. 二叉搜索树的最近公共祖先 利用 BST 的有序性，比通用 LCA 算法更高效。

BST 性质速查

操作利用 BST 性质
查找比较大小，左右子树二分
验证中序是否严格递增
第K小中序第 k 个节点
LCA值在 [p, q] 范围内的最深节点
插入按查找路径找到位置

六、踩坑实录

坑一：只检查父子关系，漏了祖先约束

如开篇故事所说，只检查"左子节点 < 父节点 < 右子节点"是不够的，必须用上下界约束或中序有序性来验证整棵树的 BST 性质。

坑二：上下界用 int 导致边界值失效

节点值是 int 类型，初始上下界必须超出 int 范围。用 Integer.MIN_VALUE - 1 的想法是错的——int 溢出会变成一个正数。必须用 long 类型。

坑三：允许相等而不是严格不等

BST 的定义是左子树值严格小于父节点，右子树值严格大于父节点。验证时必须用严格不等（< minVal 或 > maxVal 是非法的，等于也是非法的）。

坑四：中序遍历版本的 prev 初始化

prev 初始化为 Long.MIN_VALUE，因为第一个中序节点可能是 Integer.MIN_VALUE，Integer.MIN_VALUE > Long.MIN_VALUE 成立，检查通过，正确。如果 prev 初始化为 Integer.MIN_VALUE，第一个节点值等于 Integer.MIN_VALUE 时，node.val <= prev 为 true，错误地返回 false。

坑五：递归版中序遍历的 prev 是实例变量

如果 Solution 对象被复用，prev 残留上次的值会导致错误。和 124 题的全局变量问题类似，确保每次调用前 prev 被正确初始化。迭代版本不存在这个问题（prev 是局部变量）。

七、总结

98 题的精髓在于理解 BST 的两个等价性质：

  1. 定义性质：任意节点的值大于左子树所有节点，小于右子树所有节点（递归地）
  2. 中序性质：中序遍历序列严格递增

两种性质各自对应一种验证思路：上下界传递 vs 中序有序性检查。两种方法都是 O(n) 时间，选哪个主要看代码风格偏好。我更喜欢中序迭代版本——代码简洁，没有全局变量，也不需要 long 类型处理边界。

BST 相关题目的通用思路：先想想是否可以利用中序有序性来简化问题。这个性质在 BST 题目里出现的频率极高。

BST 有没有让你踩过"只检查父子关系"这个坑？评论区聊聊，点个在看支持。

编辑此页
最近更新:
贡献者: xiaozhangge