LeetCode 热题 100 98. 验证二叉搜索树-EW帮帮网

LeetCode 热题 100 | 98. 验证二叉搜索树

大家好，今天我们来解决一道经典的二叉树问题——验证二叉搜索树。这道题在 LeetCode 上被标记为中等难度，要求判断给定的二叉树是否是一个有效的二叉搜索树（BST）。

问题描述

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

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

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

示例 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

解题思路

核心思想

递归验证：
- 使用递归方法，为每个节点维护一个取值范围 [min_val, max_val]。
- 对于根节点，其取值范围为 (-∞, +∞)。
- 对于左子树，更新上界为父节点的值；对于右子树，更新下界为父节点的值。
- 如果某个节点的值超出其允许范围，则该树不是有效的二叉搜索树。
中序遍历：
- 二叉搜索树的中序遍历结果是一个严格递增的序列。
- 在中序遍历过程中，维护一个全局变量 prev，记录前一个访问的节点值。
- 如果当前节点值小于等于 prev，则该树不是有效的二叉搜索树。

递归验证方法

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def validate(node, low=float('-inf'), high=float('inf')):
            if not node:
                return True
            if not (low < node.val < high):
                return False
            return (validate(node.left, low, node.val) and
                    validate(node.right, node.val, high))
        
        return validate(root)

中序遍历方法

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.prev = float('-inf')
        
        def inorder_traversal(node):
            if not node:
                return True
            if not inorder_traversal(node.left):
                return False
            if node.val <= self.prev:
                return False
            self.prev = node.val
            return inorder_traversal(node.right)
        
        return inorder_traversal(root)

复杂度分析

时间复杂度：O(n)，其中 n 是树中节点的数量。每个节点恰好被访问一次。
空间复杂度：O(h)，其中 h 是树的高度。递归调用栈的深度最多为树的高度。

示例运行

示例 1

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

示例 2

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

总结

通过递归验证或中序遍历，我们可以高效地判断一个二叉树是否为有效的二叉搜索树。递归验证方法通过维护每个节点的取值范围来确保其符合BST的性质，而中序遍历方法则利用BST中序遍历结果为严格递增序列的特性。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

LeetCode 热题 100 98. 验证二叉搜索树