验证二叉搜索树

本文介绍了验证二叉搜索树的两种解法：递归设置上下界和中序遍历判断升序，并附有详细代码实现。

Leetcode Python 二叉树递归中序遍历

阅读要点

解法一：递归设置上下界，确保每个节点值在合法范围内。
解法二：利用中序遍历升序性质，比较相邻节点值。
两种解法时间复杂度均为 O(n)，空间复杂度为 O(h)。

题目

98. 验证二叉搜索树 - 力扣（LeetCode）

解法一：递归设置上下界

思路：二叉搜索树（BST）的定义是：对于任意节点，其左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值。因此，我们可以通过递归传递一个允许的取值范围（下界 l 和上界 r）来验证每个节点是否满足条件。

步骤：

从根节点开始，初始下界为负无穷（这里用 -2^32 近似），上界为正无穷（2^32-1）。
对于当前节点，检查其值是否在 (l, r) 区间内。如果不在，则不是 BST。
递归验证左子树，此时上界更新为当前节点值，因为左子树所有节点必须小于当前节点。
递归验证右子树，此时下界更新为当前节点值，因为右子树所有节点必须大于当前节点。
如果所有节点都满足条件，则返回 True。

复杂度分析：时间复杂度 O(n)，每个节点访问一次；空间复杂度 O(h)，h 为树的高度，递归栈深度。

答案

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node, l, r):
            if not node:
                return True
            if not l < node.val < r:
                return False
            if not dfs(node.left, l, node.val):
                return False
            if not dfs(node.right, node.val, r):
                return False
            
            return True
 
        return dfs(root, 2**32 * (-1), 2**32-1)

解法二：中序遍历判断升序

思路：二叉搜索树的一个重要性质是其中序遍历结果是一个严格递增的序列。因此，我们可以通过中序遍历来验证：在遍历过程中，记录前一个节点的值，如果当前节点值不大于前一个值，则不是 BST。

步骤：

初始化一个变量 last 为负无穷（这里用 -2^32）。
递归进行中序遍历：先遍历左子树，然后访问当前节点，最后遍历右子树。
访问当前节点时，如果 node.val <= self.last，则说明不满足递增，返回 False。
否则，更新 self.last = node.val。
继续遍历右子树。
如果整个遍历完成，则返回 True。

复杂度分析：时间复杂度 O(n)，空间复杂度 O(h)。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        self.last = 2**32 * (-1)
        def dfs(node):
            if not node:
                return True
            if not dfs(node.left):
                return False
            if node.val <= self.last:
                return False
            self.last = node.val
            if not dfs(node.right):
                return False
            
            return True
        return dfs(root)

总结：两种方法都能有效验证 BST，解法一更直观，解法二利用了 BST 的性质。实际应用中可根据需要选择。