LeetCode 98. 验证二叉搜索树 详细技术解析（含多解法+避坑指南）

LeetCode 98. 验证二叉搜索树 详细技术解析含多解法避坑指南本文聚焦 LeetCode 98. 验证二叉搜索树从题目解析、核心原理、多解法实现均贴合指定代码格式、高频坑点、边界场景测试五个维度进行全方位拆解。内容兼顾新手入门与进阶实战代码注释详尽、案例贴合题目示例帮你彻底搞懂二叉搜索树的验证逻辑避开刷题中90%的易错点轻松AC此题。验证二叉搜索树BST是二叉树类题目中的高频基础题看似简单实则暗藏多个易错点如忽略“左子树所有节点小于根、右子树所有节点大于根”的核心要求而非仅比较直接子节点。本文将从题目本质出发拆解3种主流解法中序遍历、递归边界约束、迭代中序并针对每个解法的细节和坑点进行重点说明确保你不仅能写出正确代码还能理解背后的逻辑。一、题目核心解析先吃透题意再动手编码1.1 题目要求给定一个二叉树的根节点 root判断其是否是一个有效的二叉搜索树BST。有效二叉搜索树的严格定义重中之重避坑关键节点的左子树中所有节点的值都严格小于当前节点的值节点的右子树中所有节点的值都严格大于当前节点的值当前节点的左、右子树自身也必须是有效的二叉搜索树。注意定义的核心是“所有子树节点”而非仅“直接子节点”——这是新手最易踩的坑比如示例2中根节点5的右子节点4直接小于5看似明显错误但即使右子节点是6若其左子节点是3也会因35而无效。1.2 示例解析结合题目理解定义示例1输入 root [2,1,3]树结构解析根节点2左子节点1右子节点3。根节点2左子树仅节点1所有值2右子树仅节点3所有值2左子节点1无左右子树满足条件右子节点3无左右子树满足条件结论有效输出true。示例2输入 root [5,1,4,null,null,3,6]树结构解析根节点5左子节点1右子节点4右子节点4的左子节点3、右子节点6。根节点5右子节点45直接违反“右子树所有节点大于当前节点”无需继续判断补充即使右子节点是6其左子节点35也会违反条件右子树的所有节点必须大于根节点5。结论无效输出false。1.3 提示信息影响解法选择节点数目范围[1, 10⁴] —— 解法需保证时间复杂度O(n)n为节点数避免O(n²)的暴力解法如遍历每个节点检查其所有子节点节点值范围[-2³¹, 2³¹ - 1] —— 需注意边界值如最小值-2³¹递归时初始边界不能设为0或Integer.MIN_VALUE否则会出错。二、核心原理验证BST的本质二叉搜索树BST的核心特性中序遍历的结果是严格递增的序列。推导逻辑中序遍历顺序为“左→根→右”结合BST的定义左子树所有节点根节点 → 左子树中序遍历结果根节点值右子树所有节点根节点 → 右子树中序遍历结果根节点值递归下去整个树的中序遍历结果必然是严格递增的。反之若一棵二叉树的中序遍历结果是严格递增的则该树一定是有效的BST。除此之外还可通过“递归约束每个节点的取值范围”实现验证每个节点的取值必须在“父节点的左边界”和“父节点的右边界”之间左子树的右边界是父节点值右子树的左边界是父节点值。基于这两个核心逻辑我们实现3种主流解法均贴合题目要求的代码格式。三、多解法实现均贴合指定代码格式可直接复制提交所有解法均遵循题目给定的TreeNode类和Solution类格式添加详细注释兼顾可读性和正确性可直接复制到LeetCode提交通过适配Python3环境覆盖所有边界场景。解法1中序遍历递归版最易理解推荐新手核心思路利用BST中序遍历严格递增的特性递归遍历树的中序序列记录上一个节点的值每次遍历当前节点时判断其值是否严格大于上一个节点的值若出现不满足则直接返回false。代码实现贴合指定格式# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defisValidBST(self,root:Optional[TreeNode])-bool: 验证二叉搜索树中序遍历递归版 核心BST的中序遍历结果是严格递增序列 :param root: 二叉树的根节点 :return: 布尔值是否为有效BST # 定义一个列表用于记录中序遍历的上一个节点值用列表实现引用传递避免全局变量prev[-float(inf)]# 初始值设为负无穷适配节点值为-2^31的场景definorder(node):# 递归终止条件节点为空返回true空树是有效BSTifnotnode:returnTrue# 1. 递归遍历左子树若左子树无效直接返回falseifnotinorder(node.left):returnFalse# 2. 处理当前节点判断当前节点值是否严格大于上一个节点值ifnode.valprev[0]:returnFalse# 3. 更新上一个节点值为当前节点值prev[0]node.val# 4. 递归遍历右子树返回右子树的验证结果returninorder(node.right)# 从根节点开始中序遍历验证returninorder(root)关键细节避坑重点prev的初始化用[-float(‘inf’)]而非float(‘inf’)因为节点值可能为-2³¹最小整数若初始值设为0或Integer.MIN_VALUE会导致第一个节点值为-2³¹判断失败引用传递用列表prev而非普通变量因为Python中整数是不可变对象递归函数中无法直接修改外部普通变量的值列表是可变对象可实现值的传递严格递增必须用“node.val prev[0]”判断包含等于的情况因为BST要求严格小于/大于相等的节点值会导致无效。解法2递归边界约束进阶版效率更高核心思路每个节点的取值都有明确的边界约束根节点无父节点边界为负无穷正无穷即根节点值可任意取在题目给定范围内左子节点父节点的左边界不变右边界更新为父节点值左子树所有节点必须父节点值右子节点父节点的右边界不变左边界更新为父节点值右子树所有节点必须父节点值。递归验证每个节点若节点值超出边界则返回false否则递归验证其左右子树。代码实现贴合指定格式# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defisValidBST(self,root:Optional[TreeNode])-bool: 验证二叉搜索树递归边界约束版 核心每个节点的取值必须在指定的左右边界之间递归传递边界 :param root: 二叉树的根节点 :return: 布尔值是否为有效BST defvalidate(node,lower,upper):# 递归终止条件节点为空返回true空树是有效BSTifnotnode:returnTrue# 核心判断当前节点值是否超出边界lower lt; node.val lt; upperifnode.vallowerornode.valupper:returnFalse# 递归验证左子树左子树的右边界是当前节点值左边界不变left_validvalidate(node.left,lower,node.val)# 递归验证右子树右子树的左边界是当前节点值右边界不变right_validvalidate(node.right,node.val,upper)# 左右子树均有效才返回truereturnleft_validandright_valid# 初始调用根节点的边界为负无穷正无穷# 用float(inf)和-float(inf)适配节点值的最大/最小边界-2^31 ~ 2^31-1returnvalidate(root,-float(inf),float(inf))关键细节避坑重点边界传递左子树的upper是父节点值右子树的lower是父节点值严格约束所有子节点的取值范围边界判断用“node.val lower or node.val upper”包含等于的情况BST不允许相等值边界初始化用-float(‘inf’)和float(‘inf’)覆盖题目中节点值的所有可能范围避免因初始边界过窄导致误判。解法3中序遍历迭代版避免递归栈溢出核心思路与递归版中序遍历逻辑一致用栈模拟递归过程手动实现中序遍历记录上一个节点的值判断当前节点值是否严格递增。适合节点数目较多接近10⁴的场景避免递归栈溢出Python默认递归深度约1000超过会报错。代码实现贴合指定格式# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defisValidBST(self,root:Optional[TreeNode])-bool: 验证二叉搜索树中序遍历迭代版 核心用栈模拟中序遍历记录上一个节点值判断序列是否严格递增 :param root: 二叉树的根节点 :return: 布尔值是否为有效BST stack[]# 用于模拟递归栈存储待遍历的节点prev_val-float(inf)# 记录上一个节点的值初始为负无穷currentroot# 当前遍历的节点# 循环条件当前节点不为空 或 栈不为空还有节点未遍历whilecurrentorstack:# 1. 遍历左子树将所有左节点压入栈whilecurrent:stack.append(current)currentcurrent.left# 2. 弹出栈顶节点当前左子树的最左节点处理该节点currentstack.pop()# 判断当前节点值是否严格大于上一个节点值若不满足则返回falseifcurrent.valprev_val:returnFalse# 更新上一个节点值为当前节点值prev_valcurrent.val# 3. 遍历右子树currentcurrent.right# 所有节点遍历完成均满足条件返回truereturnTrue关键细节避坑重点栈的使用先压入所有左节点再弹出处理最后遍历右节点严格遵循中序遍历“左→根→右”的顺序prev_val的更新只有处理完当前节点弹出栈后才更新prev_val避免提前更新导致判断错误循环条件current or stack确保所有节点都能被遍历即使current为空栈中还有未处理的节点。四、高频坑点与避坑指南刷题必看坑点1仅判断当前节点与直接子节点的大小关系最常见错误逻辑认为“左子节点当前节点 右子节点当前节点”就是有效BST忽略了“左子树所有节点当前节点、右子树所有节点当前节点”的核心要求。反例root [5,4,6,null,null,3,7]根节点5的右子节点65但6的左子节点35此时树无效但错误逻辑会判断为有效。避坑技巧放弃“直接子节点比较”的思路采用中序遍历或边界约束的方法确保覆盖所有子节点的判断。坑点2初始边界设置错误适配边界值场景错误操作将递归边界的初始值设为0、Integer.MIN_VALUEPython中为-2147483648导致节点值为-2³¹即-2147483648时判断出错。原因题目中节点值范围包含-2³¹若初始lower设为Integer.MIN_VALUE当根节点值为-2³¹时会触发“node.val lower”返回false实际根节点可取值为-2³¹。避坑技巧初始边界统一设为 -float(‘inf’)负无穷和 float(‘inf’)正无穷覆盖所有可能的节点值。坑点3中序遍历中prev值传递错误递归版错误操作用普通变量prev记录上一个节点值而非列表导致递归函数中无法修改prev的值判断逻辑失效。原因Python中整数是不可变对象递归函数内部修改普通变量prev只会创建局部变量不会影响外部prev的值。避坑技巧用列表如prev [-float(‘inf’)]或类属性存储prev值实现引用传递确保递归过程中prev值能被正确更新。坑点4忽略“严格递增”允许节点值相等错误操作判断条件用“node.val prev_val”“node.val lower”而非“node.val prev_val”“node.val lower and node.val upper”。原因BST的定义要求“严格小于”“严格大于”相等的节点值会导致树无效如root [2,2,3]左子节点2不小于根节点2是无效BST。避坑技巧所有判断条件必须包含“严格大于”“严格小于”禁止出现“大于等于”“小于等于”。五、边界场景测试确保代码鲁棒性梳理5种高频边界场景验证所有解法的正确性确保代码能通过LeetCode所有测试用例。场景1树中只有一个节点输入root [1] 解析单个节点无左右子树满足有效BST定义 输出true场景2节点值为最小边界-2³¹输入root [-2147483648] 解析节点值为-2³¹在题目范围内无左右子树有效 输出true场景3节点值为最大边界2³¹ - 1输入root [2147483647] 解析节点值为2³¹ - 1在题目范围内无左右子树有效 输出true场景4左子树存在比根节点小的深层节点输入root [3,2,null,1] 解析中序遍历结果为[1,2,3]严格递增有效 输出true场景5右子树存在比根节点小的深层节点输入root [3,null,4,null,null,2] 解析中序遍历结果为[3,2,4]23不严格递增无效 输出false场景6存在相等节点值输入root [2,2,3] 解析左子节点2不小于根节点2违反严格递增要求无效 输出false六、解法对比与选择建议解法时间复杂度空间复杂度优点缺点适用场景中序遍历递归O(n)O(n)递归栈深度最坏情况为链表逻辑简单、易理解、代码简洁节点过多时可能栈溢出新手入门、节点数较少的场景递归边界约束O(n)O(n)递归栈深度逻辑严谨、效率高可提前终止判断理解难度略高于中序遍历进阶学习、面试首选体现逻辑思维中序遍历迭代O(n)O(n)栈存储节点无栈溢出风险稳定性高代码略繁琐节点数多接近10⁴的场景总结面试中优先选择「递归边界约束」解法既体现对BST本质的理解又能展示严谨的逻辑思维日常刷题可选择「中序遍历递归版」简洁高效节点数较多时用「中序遍历迭代版」避免栈溢出。七、面试高频提问拓展延伸提问1为什么BST的中序遍历是严格递增的答结合BST的定义中序遍历“左→根→右”左子树所有节点根节点右子树所有节点根节点递归下去序列必然严格递增。提问2如果树中存在重复节点还能是有效的BST吗答不能BST要求左子树严格小于当前节点右子树严格大于当前节点重复节点会违反该定义。提问3递归版中为什么要用列表存储prev值答Python中整数是不可变对象递归函数内部无法修改外部普通变量的值列表是可变对象可实现引用传递确保prev值在递归过程中被正确更新。提问4如何优化递归版的空间复杂度答可使用Morris中序遍历实现O(1)空间复杂度的中序遍历进而验证BST进阶拓展适合展示代码功底。八、总结LeetCode 98. 验证二叉搜索树的核心是「吃透BST的严格定义」避免陷入“仅判断直接子节点”的误区。本文提供的3种解法中序遍历递归、递归边界约束、中序遍历迭代均贴合题目要求的代码格式可直接复制提交覆盖所有边界场景。解题关键的是要么利用“中序遍历严格递增”的特性要么通过“递归传递边界”约束每个节点的取值范围同时避开边界值、prev值传递、严格递增等易错点。建议在实际刷题中先理解递归边界约束的逻辑最能体现BST的本质再练习中序遍历的两种实现方式结合边界场景测试彻底掌握此题为后续解决二叉树的进阶题目如BST的搜索、插入、删除打下基础。若你在刷题中遇到其他易错点或有更优的解法欢迎在评论区留言交流共同完善解题思路。