20250202-leetcode98验证二叉搜索树

题目描述

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

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

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

解题思路

要验证一个二叉树是否为有效的二叉搜索树，我们需要：

确保当前节点的值大于左子树的所有节点
确保当前节点的值小于右子树的所有节点
递归验证左右子树也满足BST的性质

关键在于维护每个节点值的合法范围。我们可以通过递归时传递上下界来实现这一点。

代码实现

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 validate(node, low=float('-inf'), high=float('inf')):
            # 空节点认为是有效的BST
            if not node:
                return True
                
            # 判断当前节点值是否在合法范围内
            if node.val <= low or node.val >= high:
                return False
                
            # 递归验证左右子树
            # 左子树的所有节点值必须小于当前节点值
            # 右子树的所有节点值必须大于当前节点值
            return validate(node.left, low, node.val) and validate(node.right, node.val, high)
        
        return validate(root)




## 二叉树的遍历方式

在解决二叉树问题时，通常有以下几种遍历方式：

### 1. 前序遍历 (根-左-右)
```python
def preorder_traversal(root):
    result = []
    
    def preorder(node):
        if not node:
            return
        # 先访问根节点
        result.append(node.val)
        # 然后遍历左子树
        preorder(node.left)
        # 最后遍历右子树
        preorder(node.right)
    
    preorder(root)
    return result

2. 中序遍历 (左-根-右)

def inorder_traversal(root):
    result = []
    
    def inorder(node):
        if not node:
            return
        # 先遍历左子树
        inorder(node.left)
        # 再访问根节点
        result.append(node.val)
        # 最后遍历右子树
        inorder(node.right)
    
    inorder(root)
    return result

3. 后序遍历 (左-右-根)

def postorder_traversal(root):
    result = []
    
    def postorder(node):
        if not node:
            return
        # 先遍历左子树
        postorder(node.left)
        # 再遍历右子树
        postorder(node.right)
        # 最后访问根节点
        result.append(node.val)
    
    postorder(root)
    return result

4. 层序遍历（广度优先）

from collections import deque

def level_order_traversal(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

对于验证二叉搜索树的问题，中序遍历是一个特别有用的方法，因为二叉搜索树的中序遍历结果应该是一个递增序列。我们也可以用这种方式来验证一个二叉树是否是BST：

def isValidBST_inorder(root):
    prev = float('-inf')
    
    def inorder(node):
        nonlocal prev
        if not node:
            return True
            
        # 遍历左子树
        if not inorder(node.left):
            return False
            
        # 检查当前节点值是否大于前一个节点值
        if node.val <= prev:
            return False
        prev = node.val
            
        # 遍历右子树
        return inorder(node.right)
        
    return inorder(root)