88.验证二叉搜索树

题目

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

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

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

示例 1：

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

示例 2：

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

提示：

• 树中节点数目范围在[1, 104] 内
• -231 <= Node.val <= 231 - 1

思路

只比较根节点比左节点大，且比右节点小时不对的，因为:

        5
       / \
      1   6
         / \
        3   7

虽然都满足比较判断，但这是不对的。

中序遍历检查是否严格递增（推荐）

不仅 BST 的中序必然升序，反过来，中序升序的二叉树也必然是 BST。所以只要遍历一遍，发现任何一处 当前值 <= 前一个值，立刻判定不合法。

用上面那棵阴险的树验证：

        5
       / \
      1   6
         / \
        3   7

中序遍历：1 → 5 → 3 → 6 → 7

走到 3 时发现 3 <= 5（前一个是 5），逆序了，返回 false ✅

class Solution {

    // 状态放在类上，所有递归层共享同一份
    private var prev: Int? = null      // 中序意义上的上一个值，null 表示还没有前驱
    private var valid = true           // 一旦发现逆序就置为 false

    /**
     * 验证二叉搜索树 —— 中序遍历检查严格递增
     *
     * 核心思想：BST ⟺ 中序遍历结果严格升序。
     *          把"所有节点"这个跨层约束，转化为"相邻两项比较"。
     *
     * 时间复杂度 O(n)：每个节点访问一次（有剪枝时通常更早退出）
     * 空间复杂度 O(h)：h 为树高（递归栈），链状树退化为 O(n)
     */
    fun isValidBST(root: TreeNode?): Boolean {
        // ⚠️ 用成员变量必须在入口重置，否则同一实例调用两次会带上次的残留
        prev = null
        valid = true

        inorder(root)
        return valid
    }

    private fun inorder(node: TreeNode?) {
        // 空节点直接返回；已经判定失败也没必要继续（剪枝）
        if (node == null || !valid) return

        inorder(node.left)                      // ① 左

        // ② 根：和中序意义上的前一个值比较
        prev?.let { p ->
            // 必须用 <= ：相等也不合法（BST 要求严格大于/小于）
            if (node.`val` <= p) {
                valid = false
                return                          // 提前收手，不再往下走
            }
        }
        prev = node.`val`                       // 我成为下一个节点的前驱

        inorder(node.right)                     // ③ 右
    }
}

复杂度

• 时间复杂度:
• 空间复杂度:

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!