LeetCode 98 验证二叉搜索树：区间约束 DFS 与中序遍历多语言实现指南

LeetCode 98 验证二叉搜索树区间约束 DFS 与中序遍历多语言实现指南【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 98「验证二叉搜索树Validate Binary Search Tree」展开以仓库中的 提示文档 为主线结合 完整题解文章 与 13 种语言的 仓库源码实现系统讲解如何判断一棵二叉树是否满足 BST 性质。读完本文你将掌握暴力解、带区间约束的 DFS、BFS 以及基于中序遍历的多种解法理解只与父节点比较这一经典误区并能在实际工程中用区间上下界或Long/null边界规避整数溢出陷阱。前置知识在动手实现前需要先确认以下三个基础概念已经牢固掌握BST 性质左子树所有节点的值严格小于当前节点右子树所有节点的值严格大于当前节点且对每个子树递归成立树的遍历DFS/BFS能够以深度优先或广度优先的方式访问每个节点递归传参通过递归调用把合法取值范围这一约束逐层向下传递。其中严格小于 / 严格大于这一点至关重要它决定了 BST 中不允许出现重复值也决定了边界比较必须使用与而不是与。一、暴力解法逐节点扫描子树思路最直接的想法是对每一个节点扫描它的整棵左子树确认所有值都 node.val再扫描整棵右子树确认所有值都 node.val然后递归地对左右孩子重复同样的过程。class Solution: left_check staticmethod(lambda val, limit: val limit) right_check staticmethod(lambda val, limit: val limit) def isValidBST(self, root: Optional[TreeNode]) - bool: if not root: return True if (not self.isValid(root.left, root.val, self.left_check) or not self.isValid(root.right, root.val, self.right_check)): return False return self.isValidBST(root.left) and self.isValidBST(root.right) def isValid(self, root: Optional[TreeNode], limit: int, check) - bool: if not root: return True if not check(root.val, limit): return False return (self.isValid(root.left, limit, check) and self.isValid(root.right, limit, check))复杂度时间复杂度$O(n^2)$ —— 高层节点反复扫描其子树中的每个节点空间复杂度$O(n)$ —— 递归栈深度与树高相关最坏情况下退化为链表。暴力法正确但低效同一棵子树会被多次重复校验。提示文档 Hint 1 明确指出更好的思路是在遍历过程中跟踪取值范围tracking values during the traversal。二、DFS 区间约束法推荐的 $O(n)$ 解法核心直觉二叉搜索树不仅是每个节点与父节点比较大小每个节点必须落在由所有祖先共同决定的合法取值区间内根节点的合法区间是(-∞, ∞)进入左子树时值必须小于父节点因此区间上界收紧为父节点值进入右子树时值必须大于父节点因此区间下界收紧为父节点值。沿树向下移动的过程中区间不断收紧一旦某个节点跳出它应处的区间整棵树就不是 BST。这正是 Hint 2 描述的用区间定义子树中节点值的上下限并随遍历逐层更新以及 Hint 3 描述的检查左子树时更新最大值上限、检查右子树时更新最小值下限。算法步骤从根节点出发初始合法区间为(-∞, ∞)对每个节点若node.val不满足left node.val right返回false递归校验左子树区间更新为(left, node.val)与右子树区间更新为(node.val, right)所有节点都满足区间约束则返回true。Python 实现class Solution: def isValidBST(self, root: Optional[TreeNode]) - bool: def valid(node, left, right): if not node: return True if not (left node.val right): return False return valid(node.left, left, node.val) and valid( node.right, node.val, right ) return valid(root, float(-inf), float(inf))这段实现与仓库中 python/0098-validate-binary-search-tree.py 完全一致以float(-inf)和float(inf)作为无穷边界递归时分别用node.val替换左子树的右边界、右子树的左边界。仓库中不同语言的边界处理范式仓库对边界值的选择体现了不同语言的工程考量Ccpp/0098-validate-binary-search-tree.cpp使用LONG_MIN/LONG_MAX作为初始边界规避int溢出class Solution { public: bool isValidBST(TreeNode* root) { return helper(root, LONG_MIN, LONG_MAX); } private: bool helper(TreeNode* root, long left, long right){ if (!root) return true; if (root-val right root-val left){ return helper(root-left, left, root-val) helper(root-right, root-val, right); } return false; } };Java / Kotlinjava/0098-validate-binary-search-tree.java改用Long.MIN_VALUE/Long.MAX_VALUE或Integer包装类型的null表示无穷class Solution { public boolean isValidBST(TreeNode root) { if (root null) return true; return dfs(root, null, null); } private boolean dfs(TreeNode root, Integer min, Integer max) { if (root null) return true; if ((min ! null root.val min) || max ! null root.val max) { return false; } return dfs(root.left, min, root.val) dfs(root.right, root.val, max); } }Gogo/0098-validate-binary-search-tree.go直接把边界节点指针传入比较时取min.Val与max.Valnil即表示无边界func isValid(root, min, max *TreeNode) bool { if root nil { return true } if min ! nil root.Val min.Val { return false } if max ! nil root.Val max.Val { return false } return isValid(root.Left, min, root) isValid(root.Right, root, max) }TypeScripttypescript/0098-validate-binary-search-tree.ts使用number | nullnull代表无边界。复杂度时间复杂度$O(n)$每个节点恰好访问一次空间复杂度$O(n)$递归栈深度最坏为树高退化为链表时。三、BFS 解法用队列逐层校验思路区间约束的思想与 DFS 完全相同区别在于用队列代替递归栈逐层level by level出队校验树为空直接返回true将(root, -∞, ∞)入队循环直到队列为空弹出(node, leftBound, rightBound)若node.val不在(leftBound, rightBound)内则返回false左孩子以(leftBound, node.val)入队右孩子以(node.val, rightBound)入队全部通过则返回true。class Solution: def isValidBST(self, root: Optional[TreeNode]) - bool: if not root: return True q deque([(root, float(-inf), float(inf))]) while q: node, left, right q.popleft() if not (left node.val right): return False if node.left: q.append((node.left, left, node.val)) if node.right: q.append((node.right, node.val, right)) return True复杂度时间复杂度$O(n)$空间复杂度$O(n)$队列最坏情况下容纳一整层节点。四、补充解法中序遍历的单调性仓库源码还提供了一条完全不同的思路对 BST 进行中序遍历得到的结果必然是严格递增序列。利用这一点只需在中序遍历过程中检查prev curr是否成立。cpp/0098-validate-binary-search-tree.cpp 注释区给出了递归与显式栈两种中序遍历实现bool inorder(TreeNode* root, TreeNode* prev) { if (root NULL) return true; if (!inorder(root-left, prev)) return false; if (prev ! NULL prev-val root-val) return false; prev root; if (!inorder(root-right, prev)) return false; return true; }rust/0098-validate-binary-search-tree.rs 的实现最为简洁——完整中序遍历后检查相邻元素是否严格递增pub fn is_valid_bst(root: OptionRcRefCellTreeNode) - bool { Self::inorder(root).windows(2).all(|window| window[0] window[1]) }从源码结构看中序遍历法的时间复杂度同样为 $O(n)$且能天然规避区间边界问题其代价是额外存储中序序列或维护prev指针。五、常见陷阱1. 只与直接父节点比较最常见的错误是仅检查left.val node.val right.val对直接孩子成立。例如根为 10、左孩子为 5、而 5 的右孙子为 15局部比较全部通过但 15 大于祖先 10破坏了 BST 性质。合法区间必须从所有祖先继承这也是 DFS/BFS 区间法相对暴力解的核心优势。2. 使用了含边界的比较BST 要求严格小于 / 严格大于若误用或会错误接受含重复值的树。所有正确实现含仓库各语言版本都坚持left node.val right的严格比较。3. 整数边界溢出当用Integer.MIN_VALUE/Integer.MAX_VALUE作为初始边界时一旦树中恰好包含该极值节点node.val Integer.MAX_VALUE永远不成立导致误判。解决方案有三种仓库均有对应实现语言边界方案仓库文件CLONG_MIN/LONG_MAX提升为longcpp/0098-validate-binary-search-tree.cppJava / KotlinLong.MIN_VALUE/Long.MAX_VALUE或Integer包装类型null表示无穷java/0098-validate-binary-search-tree.javaGo传边界节点指针nil表示无边界go/0098-validate-binary-search-tree.goPython / JavaScript / Swiftfloat(-inf)/float(inf)或-Infinity/Infinitypython/0098-validate-binary-search-tree.py六、多语言对照与仓库索引本仓库为本题提供了 13 种语言的完整实现除上文引用外还包括c/0098-validate-binary-search-tree.ccsharp/0098-validate-binary-search-tree.csjavascript/0098-validate-binary-search-tree.jskotlin/0098-validate-binary-search-tree.ktswift/0098-validate-binary-search-tree.swift阅读这些实现时建议对照 完整题解文章 中的分步算法说明观察同一算法在不同语言里如何处理边界类型与空值语义。总结验证二叉搜索树的核心方法论可以浓缩为三点约束必须来自全部祖先不能只看父节点区间传递是 $O(n)$ 解法DFS 或 BFS的统一骨架——向下走时用当前节点值收紧一侧边界边界表示要防溢出用更宽的类型long或可空类型null表示无穷。掌握区间约束法后你不仅能通过本题还能自然迁移到 最大 BST 子树 等衍生问题——后者正是基于子树是否满足区间约束这一思想的直接延伸。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考