LeetCode 98. 验证二叉搜索树

Categories:

Tags:

题目描述
思路分析
1. 解法一：中序遍历（推荐）
2. 解法二：递归上下界
相似题目

题目描述

✅ 98. 验证二叉搜索树

思路分析

解法一：中序遍历（推荐）

核心思路：

BST 的中序遍历（左-根-右）结果必须严格递增，利用这一性质进行验证。

使用迭代栈模拟中序遍历，维护上一个访问节点 pre，初始为 null。

若当前节点值 <= pre.val，说明不满足严格递增，直接返回 false。

遍历完所有节点均满足则返回 true。

复杂度分析：

时间复杂度：O(n)，其中 n 为树的节点数，每个节点恰好访问一次

空间复杂度：O(h)，其中 h 为树的高度，栈最多存储 h 个节点

class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        // 记录中序遍历的上一个节点
        TreeNode pre = null;
        while (cur != null || !stack.isEmpty()) {
            // 一直向左压栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 弹栈访问节点
            cur = stack.pop();
            // 当前节点值必须严格大于前驱节点值
            if (pre != null && cur.val <= pre.val) {
                return false;
            }
            pre = cur;
            // 转向右子树
            cur = cur.right;
        }
        return true;
    }
}

func isValidBST(root *TreeNode) bool {
    stack := []*TreeNode{}
    // 记录中序遍历的上一个节点
    var pre *TreeNode
    cur := root

    for cur != nil || len(stack) > 0 {
        // 一直向左压栈
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        // 弹栈访问节点
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        // 当前节点值必须严格大于前驱节点值
        if pre != nil && cur.Val <= pre.Val {
            return false
        }
        pre = cur
        // 转向右子树
        cur = cur.Right
    }

    return true
}

解法二：递归上下界

核心思路：

每个节点合法的值范围由其所有祖先节点共同约束，而非仅与直接父节点比较。

定义递归函数 isValid(node, min, max)，要求 node.val 必须严格在开区间 (min, max) 内。

根节点调用 isValid(root, -∞, +∞)。

递归左子树时，上界收紧为当前节点值：isValid(node.left, min, node.val)。

递归右子树时，下界收紧为当前节点值：isValid(node.right, node.val, max)。

常见错误：只比较节点与直接子节点大小关系，忽略整棵子树的范围约束。

复杂度分析：

时间复杂度：O(n)，其中 n 为树的节点数，每个节点恰好访问一次

空间复杂度：O(h)，其中 h 为树的高度，递归调用栈深度

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

    // 验证节点值是否严格在 (min, max) 范围内
    private boolean isValid(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }
        // 当前节点值必须严格在上下界之间
        if (node.val <= min || node.val >= max) {
            return false;
        }
        // 左子树上界收紧为当前节点值，右子树下界收紧为当前节点值
        return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
    }
}

func isValidBST(root *TreeNode) bool {
    return isValid(root, math.MinInt64, math.MaxInt64)
}

// 验证节点值是否严格在 (min, max) 范围内
func isValid(node *TreeNode, min, max int) bool {
    if node == nil {
        return true
    }
    // 当前节点值必须严格在上下界之间
    if node.Val <= min || node.Val >= max {
        return false
    }
    // 左子树上界收紧为当前节点值，右子树下界收紧为当前节点值
    return isValid(node.Left, min, node.Val) && isValid(node.Right, node.Val, max)
}

相似题目

题目	难度	考察点
94. 二叉树的中序遍历	简单	二叉树、中序遍历
230. 二叉搜索树中第 K 小的元素	中等	BST、中序遍历
501. 二叉搜索树中的众数	简单	BST、中序遍历
235. 二叉搜索树的最近公共祖先	中等	BST 性质、递归
669. 修剪二叉搜索树	中等	BST、递归
700. 二叉搜索树中的搜索	简单	BST 性质
1382. 将二叉搜索树变平衡	中等	BST、中序遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/83568790