98. 验证二叉搜索树 (Medium)

专题归类： 05-二叉树 LeetCode 链接： https://leetcode.cn/problems/validate-binary-search-tree/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

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

有效 BST 定义如下：

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

示例 1：

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

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5，但右子节点的值是 4。

提示：

• 树中节点数目范围在 [1, 10^4] 内
• -2^31 <= Node.val <= 2^31 - 1

---

题目详细分析

• 数据范围含义： 最多 10000 节点，递归深度可能达到 10000。节点值覆盖整个 32 位整数范围，不能用 ±∞ 的 int 表示，需要用 Python 的 float('-inf') 和 float('inf') 或 None 哨兵。
• 输入输出特征： 输入根节点，输出布尔值。
• 边界条件： 单节点返回 True；空树？题目节点数 >= 1。
• 核心约束： BST 的全局约束性质——不仅要保证 左子节点 < 当前节点 < 右子节点，还必须保证 左子树的所有节点 都小于当前节点，右子树的所有节点 都大于当前节点。
• 隐藏条件： BST 不允许重复值（严格小于/大于）。中序遍历结果应该是 严格递增 的。

---

小白版直白理解

就像检查一个家族族谱的辈分规则——家族规定：所有在左边分支的后代必须比老祖宗年轻，所有在右边分支的后代必须比老祖宗年长。而且这条规则在每个分支的节点上都适用：左边分支内部也是「左边的后代更年轻，右边的后代更年长」。你不能只检查每个人和直接父母的关系，还要检查全局上是否都符合这个大小顺序。

---

解题思路

思路一：中序遍历递归（推荐）

核心思想： BST 的中序遍历结果是 严格递增 的序列。用全局变量 prev 记录上一个访问的节点值，在中序位置检查 当前值 > prev，如果不满足则不是 BST。

为什么用中序？ BST 最核心的性质就是中序递增。利用这个性质来验证是最简洁、最不容易出错的方法。中序位置（左子树回来后）正好拿到了左子树处理完的状态，可以自然地与前一个值比较。

def isValidBST(root):
    prev = float('-inf')  # 上一个节点的值（初始为负无穷）
 
    def inorder(node):
        nonlocal prev
        if not node:
            return True
 
        # 左：递归检查左子树
        if not inorder(node.left):
            return False
 
        # 根：检查当前节点值是否大于前一个值
        if node.val <= prev:   # 注意是 <=，严格递增
            return False
        prev = node.val
 
        # 右：递归检查右子树
        return inorder(node.right)
 
    return inorder(root)

思路二：上下界传递法

核心思想： 每个节点都有一个允许的取值范围 (low, high)。根节点的范围是 (-∞, +∞)。左子树的节点必须在 (low, root.val) 范围内，右子树的节点必须在 (root.val, high) 范围内。递归传递这个范围，一旦发现节点值超出范围就返回 False。

为什么这种方法也有效？ 它直接体现了 BST 的全局约束——每个节点都有一个从根节点路径上累积下来的取值范围。这种方式不需要中序遍历，前序/后序都可以。

def isValidBST(root, low=float('-inf'), high=float('inf')):
    if not root:
        return True
 
    # 检查当前节点是否在合法范围内
    if root.val <= low or root.val >= high:
        return False
 
    # 左子树：上界变为 root.val
    # 右子树：下界变为 root.val
    return (isValidBST(root.left, low, root.val) and
            isValidBST(root.right, root.val, high))

思路三：中序遍历迭代法

用栈模拟中序遍历，在遍历过程中检查是否递增。可以提前终止（一旦发现不递增就停止）。

def isValidBST(root):
    stack = []
    cur = root
    prev = float('-inf')
 
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
 
        # 检查是否递增
        if cur.val <= prev:
            return False
        prev = cur.val
 
        cur = cur.right
 
    return True

---

易错点

• 不能只检查左右子节点： 很多初学者写 if root.left.val >= root.val or root.right.val <= root.val。这是错的！因为右子树的左子节点可能小于根节点，但仍大于右子节点。必须全局约束。
• 等号的处理： BST 要求严格小于/大于，所以检查条件是 <= 和 >= 而不是 < 和 >。
• int 边界问题： 节点值范围是 [-2^31, 2^31-1]，用 float('-inf') 和 float('inf') 是最安全的。
• 递归中的短路返回： 当左子树不是 BST 时，应该立即返回 False，不需要继续检查。中序法通过 if not inorder(node.left): return False 实现了短路。

---

框架提炼

BST 中序遍历递增模板：

prev = -inf
def inorder(node):
    if not node: return True
    if not inorder(node.left): return False   # 左
    if node.val <= prev: return False          # 根：检查递增
    prev = node.val
    return inorder(node.right)                 # 右

BST 上下界验证模板：

def validate(node, low, high):
    if not node: return True
    if node.val <= low or node.val >= high: return False
    return validate(node.left, low, node.val) and \
           validate(node.right, node.val, high)

---

关联题目

• 94-二叉树的中序遍历 — 中序遍历是验证 BST 的基础，先掌握中序遍历的递归和迭代写法。
• 230-BST第K小的元素 — 利用 BST 中序递增的性质找第 k 小元素，是本题中序法的直接应用。
• 108-将有序数组转换为二叉搜索树 — 构建 BST 的过程反过来也是验证 BST 的基础。