LeetCode 98：验证二叉搜索树 | 中序遍历

LeetCode 98验证二叉搜索树 | 中序遍历一、题目详解1.1 题目描述LeetCode 98验证二叉搜索树Validate Binary Search Tree给你一个二叉树的根节点root判断其是否是一个有效的二叉搜索树BST。有效BST定义节点的左子树只包含小于当前节点的数节点的右子树只包含大于当前节点的数所有左子树和右子树自身必须也是二叉搜索树难度Medium示例 1输入root [2,1,3] 输出true示例 2输入root [5,1,4,null,null,3,6] 输出false 解释根节点的值是 5 但是右子节点的值是 4 。1.2 题目分析二叉搜索树BST的核心性质中序遍历结果是有序的。判断BST的关键左子树所有节点 根节点右子树所有节点 根节点左右子树都是BST二、算法实现2.1 递归法def isValidBST(root): def validate(node, low, high): if not node: return True # 当前节点值必须在(low, high)范围内 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, float(-inf), float(inf))递归思路解析定义辅助函数传入当前节点和允许的取值范围(low, high)如果当前节点为空返回True空树是BST如果当前节点值不在范围内返回False递归验证左子树范围变为(low, node.val)递归验证右子树范围变为(node.val, high)2.2 中序遍历法def isValidBST_inorder(root): stack [] prev float(-inf) current root while current or stack: # 深入左子树 while current: stack.append(current) current current.left # 访问当前节点 current stack.pop() if current.val prev: return False prev current.val # 转向右子树 current current.right return True中序遍历思路解析使用栈进行中序遍历记录前一个节点的值如果当前节点值 前一个节点值说明不是BST2.3 Morris遍历法O(1)空间def isValidBST_morris(root): prev float(-inf) current root while current: if not current.left: # 访问当前节点 if current.val prev: return False prev current.val current current.right else: # 找到前驱节点 predecessor current.left while predecessor.right and predecessor.right ! current: predecessor predecessor.right if not predecessor.right: predecessor.right current current current.left else: # 恢复树结构并访问 predecessor.right None if current.val prev: return False prev current.val current current.right return True三、复杂度分析3.1 递归法时间复杂度O(n)每个节点访问一次空间复杂度O(h)递归调用栈深度3.2 中序遍历法时间复杂度O(n)每个节点入栈出栈一次空间复杂度O(h)栈的最大深度3.3 Morris遍历法时间复杂度O(n)空间复杂度O(1)不使用额外空间四、边界情况讨论4.1 空树root None # 输出True空树是BST4.2 单节点树root TreeNode(1) # 输出True4.3 普通BST# 4 # / \ # 2 6 # / \ / \ # 1 3 5 7 # 输出True4.4 无效BST右子树有小于根的节点# 5 # / \ # 1 4 # / \ # 3 6 # 输出False4 54.5 边界值测试# 测试int边界值 root TreeNode(2147483647) # 最大int值 # 输出True五、常见错误分析5.1 错误只比较父子节点# ❌ 错误实现 def isValidBST_wrong(root): if not root: return True if root.left and root.left.val root.val: return False if root.right and root.right.val root.val: return False return isValidBST_wrong(root.left) and isValidBST_wrong(root.right)问题只比较了父子节点但BST要求整个左子树都小于根整个右子树都大于根。# 这个树会被错误判断为True # 5 # / \ # 1 6 # / \ # 3 7 # 实际应该返回False3 55.2 正确做法传递范围约束# ✅ 正确实现 - 传递上下界 def isValidBST(root): def validate(node, low, high): 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, float(-inf), float(inf))六、总结6.1 核心要点要点说明递归法传递范围约束验证每个节点中序遍历利用BST中序遍历有序的性质Morris遍历O(1)空间复杂度关键必须验证整个子树的范围而非仅父子节点6.2 方法对比方法优点缺点递归法直观容易理解可能栈溢出中序遍历利用BST特性需要额外空间Morris遍历O(1)空间代码复杂修改树结构6.3 扩展思考如何修复一个无效的BST如何找到BST中违反性质的节点BST的其他性质有哪些应用参考资料LeetCode 98 题解二叉搜索树定义