教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文基于 AlgoNote「算法通关手册」仓库中的 validate-binary-search-tree.md 题解文档系统讲解 LeetCode 第 0098 题「验证二叉搜索树」的完整解法。你将掌握二叉搜索树BST的定义与核心性质、基于「区间约束」的递归校验法、基于「中序遍历递增」的验证法以及显式栈迭代实现并理解题目边界条件与复杂度分析能够举一反三解决同系列 BST 校验类问题。题目概况题号0098. 验证二叉搜索树Validate Binary Search Tree标签树、深度优先搜索、二叉搜索树、二叉树难度中等题目大意给定一个二叉树的根节点root判断其是否是一棵有效的二叉搜索树。题目约束树中节点数目范围在 $[1, 10^4]$ 内。节点取值范围$-2^{31} \le Node.val \le 2^{31} - 1$。示例 1输入root [2,1,3] 输出true示例 2输入root [5,1,4,null,null,3,6] 输出false 解释根节点的值是 5 但是右子节点的值是 4 。二叉搜索树的定义回顾在动手解题前需要先明确 BST 的严格定义。仓库中的 05_04_binary_search_tree.md 给出了权威表述对于任意节点如果其左子树非空则左子树所有节点的值均小于该节点的值对于任意节点如果其右子树非空则右子树所有节点的值均大于该节点的值任意节点的左右子树也都分别是二叉搜索树递归定义。其核心特性可以浓缩为一行左子树所有节点值 根节点值 右子树所有节点值注意这里的两个关键词「所有」和「严格」。这决定了验证时不能只比较父节点与直接子节点而必须保证整棵子树的范围都落在合法区间内这正是本题最容易出错的地方示例 2 中右子节点 4 小于根节点 5虽然 4 大于其父节点 1但整体违反了 BST 性质。另一个重要推论同样来自该文档对二叉搜索树进行中序遍历得到的节点值序列一定是严格递增的。这一性质是思路 2 的理论基础。思路 1区间约束递归遍历官方题解核心方法算法思路本题的核心解法是「带上下界的前序递归遍历」。前序、中序、后序遍历都可以实现这里以前序遍历为例设计递归函数preorderTraversal(root, min_v, max_v)其中min_v、max_v表示当前节点合法取值区间(min_v, max_v)开区间。前序遍历时先判断根节点的值是否落在(min_v, max_v)之间如果不在直接返回False如果在区间内继续递归检测左右子树是否满足左右子树都满足才是一棵二叉搜索树。递归遍历左子树时要将上界max_v更新为当前根节点的值——因为左子树上所有节点的值都必须小于根节点递归遍历右子树时要将下界min_v更新为当前根节点的值——因为右子树上所有节点的值都必须大于根节点。整个递归过程不断把「祖先节点的值」向下传递并收紧区间从而保证不仅是父与子的局部关系正确而是整棵子树范围全局正确。参考代码class Solution: def isValidBST(self, root: TreeNode) - bool: def preorderTraversal(root, min_v, max_v): if root None: return True if root.val max_v or root.val min_v: return False return preorderTraversal(root.left, min_v, root.val) and preorderTraversal(root.right, root.val, max_v) return preorderTraversal(root, float(-inf), float(inf))关键参数说明参数含义取值与说明root当前递归子树的根节点为None时空子树合法返回Truemin_v当前节点值的下界开区间初始为float(-inf)进入右子树时更新为父节点值max_v当前节点值的上界开区间初始为float(inf)进入左子树时更新为父节点值比较运算符与严格比较使用/判定非法杜绝重复值混入 BST为什么使用float(-inf)/float(inf)作初值因为节点值范围覆盖整个 32 位整数区间 $[-2^{31}, 2^{31}-1]$根节点没有天然的上下界约束只有用「负无穷/正无穷」才能保证第一次比较恒为合法。若改用有限值如 0当节点值恰好小于该值时会误判。复杂度分析时间复杂度$O(n)$其中 $n$ 是二叉树的节点数目每个节点恰好被访问一次。空间复杂度$O(n)$。递归函数需要用到系统调用栈空间栈空间取决于递归深度最坏情况下树退化为单链表递归深度为 $n$所以空间复杂度为 $O(n)$。思路 2中序遍历验证递增序列算法思路基于「BST 中序遍历结果严格递增」的性质见 05_04_binary_search_tree.md 与 05_02_binary_tree_traverse.md可以换一种等价解法对二叉树进行中序遍历得到节点值序列检查序列是否严格递增相邻元素满足prev current若序列中存在prev current则说明不是二叉搜索树返回False。这一思路在仓库同类题解中得到了大量印证例如 0099. 恢复二叉搜索树 正是利用「BST 中序遍历为有序序列」的性质通过查找两个逆序对来定位被错误交换的两个节点0094. 二叉树的中序遍历 则提供了完整的中序遍历实现模板。参考代码递归版class Solution: def isValidBST(self, root: TreeNode) - bool: 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)这里的prev记录中序遍历中上一个被访问的节点值采用「边遍历边校验」的方式无需额外存储整个遍历序列空间上只额外占用 $O(1)$ 的变量递归栈仍为 $O(n)$。思路 3显式栈迭代实现避免递归栈溢出算法思路递归实现依赖系统调用栈当树退化为链表、节点数达到 $10^4$ 量级时存在栈溢出风险。此时可以借鉴 0094. 二叉树的中序遍历 思路 2 的「模拟栈」技巧用显式栈手工模拟中序遍历过程并在遍历过程中同步校验递增性。迭代中序遍历的核心原则是在左子树访问完毕之前当前节点不能提前出栈。具体步骤从根节点开始不断将当前子树根节点入栈并走向左子树直到无左子树弹出栈顶节点并访问校验该值与上一个值的大小关系转向弹出节点的右子树重复上述过程。参考代码迭代 校验class Solution: def isValidBST(self, root: Optional[TreeNode]) - bool: stack [] prev float(-inf) while root or stack: while root: stack.append(root) # 左子树不断入栈 root root.left node stack.pop() # 访问最左侧节点 if node.val prev: # 校验递增性 return False prev node.val root node.right # 转向右子树 return True时间复杂度$O(n)$每个节点入栈、出栈各一次。空间复杂度$O(n)$显式栈最坏情况下存放整条左链。边界情况与易错点总结必须使用严格不等号BST 不允许重复值若节点值等于边界值root.val max_v或root.val min_v即为非法。如果使用非严格比较会放过重复值导致错误答案。不能只比较父节点与子节点如示例 2[5,1,4,null,null,3,6]中节点 3 满足与父节点 1 的关系3 1但它位于根节点 5 的右子树却小于 5整体不合法。只有传递上下界思路 1或依赖中序递增思路 2才能捕获此类错误。初值选择根节点上下界必须用float(-inf)/float(inf)否则无法覆盖全 32 位整数取值区间。空子树合法root None时应当返回True空树/空子树本身满足 BST 定义。递归深度节点数可达 $10^4$退化树场景下递归版栈深为 $O(n)$可用思路 3 的显式栈替代。仓库源码级印证与同类题目拓展上述解法在仓库中有完整的知识体系支撑可继续深入阅读BST 基础理论05_04_binary_search_tree.md定义、查找、插入、删除的完整算法与代码遍历基础05_02_binary_tree_traverse.md前/中/后序遍历的递归与非递归实现中序遍历模板0094. 二叉树的中序遍历中序递增性质的应用0099. 恢复二叉搜索树通过逆序对定位两个被错误交换的节点前序序列校验0255. 验证二叉搜索树的前序遍历序列用单调栈维护下界思路与本文思路 1 的区间约束一脉相承BST 题目全集00_06_categories_list.md「二叉搜索树题目」分类下收录了 0098、0173、0700、0701、0450、0230、0235 等系列题建议在掌握本文三种思路后继续练习 0235. 二叉搜索树的最近公共祖先、0230. 二叉搜索树中第 K 小的元素 等题目进一步体会「BST 中序有序」这一核心性质在各类问题中的应用。小结验证二叉搜索树是 BST 系列题目的基石其本质是「把祖先约束向下传递」。本文覆盖了三种主流实现区间约束递归思路清晰、直接对应 BST 定义、中序遍历递增校验利用 BST 中序有序的核心性质、显式栈迭代规避递归栈溢出。三者时间复杂度均为 $O(n)$思路 1 与思路 2 的空间复杂度为 $O(n)$迭代版借助显式栈同样为 $O(n)$。掌握本题后BST 的查找、插入、删除与各类变形题恢复、序列化、构造、众数统计等都能以此为基础快速展开。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册二叉搜索树BST查找、插入、创建与删除全攻略AlgoNote 算法通关手册二叉搜索树BST查找、插入、创建与删除全攻略 导读 本文是 AlgoNote 算法通关手册 https://link.git教程文档知识库AlgoNote 算法通关手册LeetCode 0096「不同的二叉搜索树」——从动态规划到卡特兰数的计数问题全解AlgoNote 算法通关手册LeetCode 0096「不同的二叉搜索树」——从动态规划到卡特兰数的计数问题全解 本篇技术指南以「算法通关手册」AlgoNo教程文档知识库LeetCode 0094 二叉树的中序遍历递归与显式栈迭代双解法详解AlgoNote 算法通关手册LeetCode 0094 二叉树的中序遍历递归与显式栈迭代双解法详解AlgoNote 算法通关手册 本篇技术指南围绕「算法通关手册」AlgoNote 仓教程文档知识库上一篇chatgpt.js与Web API集成打造更智能的AI应用下一篇Google Ads Python 客户端库安装与使用指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考