98. 验证二叉搜索树#

生活小剧场：超市理货员的烦恼#

假设你是超市的新员工，负责整理饮料货架。主管给你两条规则：

1. 每层货架左边只能放低价商品，右边放高价商品
2. 每个商品的价格标签必须清晰可见

但有个狡猾的同事把货架搞得一团糟：

    可乐 ¥5
   /     \
雪碧 ¥4  芬达 ¥6 
     \
    脉动 ¥5.5 ← 藏在可乐左边却比可乐便宜！

你会发现虽然直接看可乐的左右没问题，但隐藏的脉动才是问题所在。这就是验证二叉搜索树的现实写照！

问题描述#

题目目标#

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效二叉搜索树满足：节点左子树只包含小于当前节点的数，右子树只包含大于当前节点的数，且左右子树本身也都必须是二叉搜索树。

示例 1#

输入： root = [2,1,3] 输出： true 二叉树示意：

 2
/ \
1 3

说明： 根节点 2 的左子树只有 1，右子树只有 3，且都满足左小右大的规则，所以结果是 true。

补充说明#

• 二叉树通常使用层序数组表示，null 表示该位置没有节点。

问题解析：到底在验证什么？#

我们需要确认这棵树满足：

1. 每个节点左边的所有子孙（不光是直接左孩子）都比它小
2. 每个节点右边的所有子孙（不光是直接右孩子）都比它大

就像检查整个货架区域，不能只看相邻商品，要确保整个左半区都符合规则。

常见错误：只检查眼前货物#

新手最容易写成这样的错误代码：

boolean check(TreeNode node) {
    // 空节点默认合法（递归终止条件）
    if (node == null) return true;
    // 只检查“当前节点与左孩子”的大小关系（这种写法会漏掉深层违规）
    if (node.left != null && node.left.val >= node.val) return false;
    // 只检查“当前节点与右孩子”的大小关系（同样不充分）
    if (node.right != null && node.right.val <= node.val) return false;
    // 继续递归检查左右子树
    return check(node.left) && check(node.right);
}

这就像只检查相邻商品：

    5
   / \
  1   6
     / \
    4   7 ← 4虽然小于6，但应该大于5！

明明4出现在5的右侧区域却比5小，这种深层问题会被漏掉。

正确方法一：传递价格标签法#

核心思想#

想象每个商品都带有两个隐形标签：

• 最低允许价格（不能比这个低）
• 最高允许价格（不能比这个高）

比如可乐（5元）的标签是：

• 左区商品：最高价 ≤5元
• 右区商品：最低价 ≥5元

具体步骤#

1. 给根节点设置初始范围（无限小到无限大）
2. 检查当前节点是否在允许范围内
3. 给左孩子设置新范围（继承父节点下限，上限设为当前值）
4. 给右孩子设置新范围（继承父节点上限，下限设为当前值）

代码示例（Java）#

public boolean isValidBST(TreeNode root) {
    // 从整棵树开始检查，初始允许范围设为 (-∞, +∞)
    return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

boolean check(TreeNode node, long minAllow, long maxAllow) {
    // 递归终止条件：空节点视为合法
    if (node == null) return true;

    // 当前节点值必须严格落在 (minAllow, maxAllow) 内
    // 用 <= 和 >= 保证“严格小于/严格大于”
    if (node.val <= minAllow || node.val >= maxAllow) return false;

    // 检查左子树：上界收紧为当前节点值
    boolean leftValid = check(node.left, minAllow, node.val);

    // 检查右子树：下界收紧为当前节点值
    boolean rightValid = check(node.right, node.val, maxAllow);

    // 仅当左右子树都合法时，当前子树才合法
    return leftValid && rightValid;
}

关键细节：

• 使用Long类型：避免数字边界问题（比如节点值是Integer.MIN_VALUE）
• 前开后闭区间：确保严格大于/小于

正确方法二：商品价格单检查法#

核心思想#

如果这是合法的BST，那么按照”左→中→右”顺序记录价格时，价格单应该是严格递增的。就像整理好的货架，从左到右价格应该一直上涨。

操作步骤#

1. 准备一个记事本记录上一个价格
2. 按照左→中→右顺序遍历货架
3. 每次记录新价格时，检查是否比上一个高

代码示例（Python）#

def isValidBST(root):
    self.last_val = -float('inf')  # 初始设为极小值

    def traverse(node):
        if not node: return True

        # 先检查左边货架
        if not traverse(node.left): return False

        # 检查当前价格
        if node.val <= self.last_val:
            return False
        self.last_val = node.val  # 更新记录本

        # 最后检查右边货架
        return traverse(node.right)

    return traverse(root)

复杂度分析#

两种方法都像检查整个货架：

• 时间：每个商品检查一次 → O(n)
• 空间：最差情况要记住整条货架的位置 → O(n)（比如货架摆成一条直线）

思维升级：为什么这两种方法有效？#

1. 边界传递法像给每个区域贴警示标签：
   

2. 中序检查法像拿着清单逐项核对：
   

常见疑问解答#

Q：为什么要用Long类型？用Integer不行吗？
A：就像货架可能有”¥-2147483648”这样的超低价商品，用Integer会导致边界判断错误。Long类型就像扩展了价格标签的范围。

Q：空树（没有商品）算合法BST吗？
A：是的！就像空货架当然符合规则。

Q：如果有重复价格怎么办？
A：BST要求严格小于/大于，重复价格就像两件同价商品放在同一层，这是不允许的。