98. 验证二叉搜索树

题目链接（中等）

题目描述

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

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

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

二叉搜索树的核心性质：左子树所有节点 < 根 < 右子树所有节点。

二叉搜索树有一个重要性质：中序遍历得到的序列一定是严格升序的。

数据范围：

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

示例

示例 1：

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

示例 2：

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

方法一：递归（上下界）

思路及解法

仅仅检查每个节点和它的左右孩子是不够的。例如：

  5
 / \
1   6
   / \
  3   7

节点 3 是 6 的左孩子，满足 3 < 6，但 3 位于根 5 的右子树中，必须大于 5，而 3 < 5，所以不是 BST。

因此，递归时需要携带上下界：以 node 为根的子树中，所有节点的值必须落在开区间 (lo, hi) 内。

• 初始调用：fun(root, -inf, +inf)；
• 进入左子树：上界收紧为 node.val，调用 fun(node.left, lo, node.val)；
• 进入右子树：下界收紧为 node.val，调用 fun(node.right, node.val, hi)；
• 若当前节点值 val 不满足 lo < val < hi，直接返回 False。

直觉理解：每个节点都有一个合法的取值区间，随着递归深入，区间不断收窄。任何节点跳出自己的区间，就不是 BST。

代码

class Solution:
    def isValidBST(self, root: TreeNode | None) -> bool:
        def fun(node, lo, hi):
            if not node:
                return True
            val = node.val
            if val <= lo or val >= hi:
                return False
            return fun(node.left, lo, val) and fun(node.right, val, hi)

        return fun(root, float('-inf'), float('inf'))

复杂度分析

• 时间复杂度：$O(n)$，每个节点最多访问一次。
• 空间复杂度：$O(n)$，递归栈深度最坏为 $n$（树退化成链）。

方法二：中序遍历（递归）

思路及解法

二叉树

中序遍历顺序：左 → 根 → 右。因为 BST 保证左子树所有值 < 根 < 右子树所有值，所以中序序列递增。

因此可以：

1. 先对二叉树做一次中序遍历，把节点值依次存进列表；
2. 再检查列表是否严格升序即可。

为什么是严格升序？ 题目要求左子树 严格小于 根、右子树 严格大于 根，所以中序序列中相邻两个值不能相等。

代码

class Solution:
    def isValidBST(self, root: TreeNode | None) -> bool:
        vals = []

        def fun(node):
            if not node:
                return
            fun(node.left)
            vals.append(node.val)
            fun(node.right)

        fun(root)

        # 检查是否严格升序
        return all(vals[i] < vals[i + 1] for i in range(len(vals) - 1))

复杂度分析

• 时间复杂度：$O(n)$，每个节点访问一次，最后检查一遍列表。
• 空间复杂度：$O(n)$，vals 列表长度为 $n$，递归栈深度最坏也为 $O(n)$。