LeetCode 98. 验证二叉搜索树

约 5 分钟
文章信息 22 个分类 6 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 50-100 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 华为 拼多多 小米 虾皮 哔哩哔哩 LeetCode 热题 100 面试经典 150 题
标签
深度优先搜索 树 二叉树 二叉搜索树 中序遍历 二叉搜索树经典题
目录

题目描述

✅ 98. 验证二叉搜索树

image-20230305213733014

image-20230305213737260

题意分析

给定一棵二叉树的根节点，判断它是不是一棵有效的二叉搜索树，返回 true 或 false。

有效的定义是：每个节点的整棵左子树中所有节点值都严格小于该节点值，整棵右子树中所有节点值都严格大于该节点值。注意是「整棵子树」而不是「左右孩子」——一个节点不仅要比它的父节点小或大，还要满足所有祖先施加的约束，这是本题最大的陷阱。同时「严格」意味着相等也算无效，树里出现重复值直接判否。

约束信号：节点数最多 $10^4$，递归深度不构成压力；但节点值的范围覆盖整个 int，也就是说节点值可能恰好取到 int 的最小值或最大值，任何用「哨兵值」表示无穷的写法都要留心这一点。

边界情况：空树按惯例视为有效；单节点树一定有效。

解法：递归传递上下界

核心思路

问题关键：BST 要求整棵左子树都小于根、整棵右子树都大于根，只比较父节点和直接孩子不够；深层节点还必须满足所有祖先留下的限制。

为什么选上下界递归：从根走向某个节点时，向左就收紧上界，向右就收紧下界。把这对边界随递归传下去，每个节点只检查一次，就能同时验证全部祖先约束。

状态与不变量：validate(node, lower, upper) 表示验证以 node 为根的子树，且该节点合法值必须落在开区间 (lower, upper)。左子树使用 (lower, node.val)，右子树使用 (node.val, upper)；当前节点和两棵子树都合法，当前子树才合法。这一递归定义完整覆盖 BST 条件，也保证重复值会被拒绝。

Java 用 long 表示超出 int 值域的初始边界；Go 用 nil 表示没有边界，避免把合法的最大、最小整数误当哨兵。中序遍历严格递增也是等价解法，但上下界更直接体现「祖先约束」。

解题步骤

  • 从根开始，初始范围设为无下界、无上界。
  • 空节点返回 true，作为递归终止条件。
  • 若当前值 <= lower 或 >= upper，违反严格区间，立即返回 false。
  • 验证左子树时将当前值作为新上界，验证右子树时将当前值作为新下界；两边都通过才返回 true。

例如 [10,5,15,null,null,6,20] 中，6 虽小于父节点 15，但它位于 10 的右子树，合法区间应是 (10,15)，因此整棵树无效。

代码实现

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }

        // 左右子树分别继承并收紧当前节点的取值范围。
        return validate(node.left, lower, node.val) && validate(node.right, node.val, upper);
    }
}

func isValidBST(root *TreeNode) bool {
    return validateBST(root, nil, nil)
}

func validateBST(node *TreeNode, lower *int, upper *int) bool {
    if node == nil {
        return true
    }
    if lower != nil && node.Val <= *lower {
        return false
    }
    if upper != nil && node.Val >= *upper {
        return false
    }

    // 递归向下传递当前子树允许的开区间边界。
    return validateBST(node.Left, lower, &node.Val) && validateBST(node.Right, &node.Val, upper)
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点最多检查一次。
  • 空间复杂度：$O(h)$，h 为树高；平衡树为 $O(\log n)$，链状树最坏为 $O(n)$。

关键点总结

  • BST 是全局的祖先区间约束，不是局部父子比较。
  • 向左收紧上界，向右收紧下界，另一侧边界必须继续继承。
  • 区间是开区间，比较要用 <=、>=，重复值不合法。
  • 初始边界不能占用合法值；可升位宽或显式表示「无界」。

易错点总结

  • 只比较直接孩子会漏掉跨层违规：[10,5,15,null,null,6,20] 应返回 false。
  • 用 int 极值作初始边界会误判合法极值节点，如单节点 [2147483647]。
  • 把区间写成闭区间会放过重复值；[2,2] 不是 BST。
  • 左右边界方向不能传反：左子树收紧上界，右子树收紧下界。

相似题目

题目 难度 考察点
99. 恢复二叉搜索树 中等 中序找逆序对，交换两个错位节点恢复 BST
230. 二叉搜索树中第 K 小的元素 中等 中序计数，第 $k$ 个访问的节点即答案
426. 将二叉搜索树转化为排序的双向链表 中等 中序遍历中原地改指针成循环双向链表
538. 把二叉搜索树转换为累加树 中等 反序中序（右—根—左）累加后缀和
897. 递增顺序搜索树 简单 中序重排成只有右孩子的单链树
1038. 从二叉搜索树到更大和树 中等 与 538 同题，练反序中序的模板写法
LCR 052. 递增顺序搜索树 简单 897 的镜像题，同一套中序拉直手法
LCR 054. 把二叉搜索树转换为累加树 中等 538 的镜像题，验证反序中序是否熟练
剑指 Offer 36. 二叉搜索树与双向链表 中等 426 的国服版，前驱后继指针的维护
剑指 Offer 54. 二叉搜索树的第k大节点 简单 反序中序计数，找第 $k$ 大而非第 $k$ 小
面试题 04.05. 合法二叉搜索树 中等 与本题同题，可换中序判据再练一遍
面试题 17.12. BiNode 简单 中序拉直成单向链表，指针断接的顺序