企业官网建设流程全解析

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 描述的"检查左子树时更新最大值上限、检查右子树时更新最小值下限"。

算法步骤

1. 从根节点出发，初始合法区间为(-∞, +∞)；
2. 对每个节点：若node.val不满足left < node.val < right，返回false；
3. 递归校验左子树（区间更新为(left, node.val)）与右子树（区间更新为(node.val, right)）；
4. 所有节点都满足区间约束，则返回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替换左子树的右边界、右子树的左边界。

仓库中不同语言的边界处理范式

仓库对边界值的选择体现了不同语言的工程考量：

• C++（cpp/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 / Kotlin（java/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); } }

• Go（go/0098-validate-binary-search-tree.go）直接把边界节点指针传入，比较时取min.Val与max.Val，nil即表示无边界：

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) }

• TypeScript（typescript/0098-validate-binary-search-tree.ts）使用number | null，null代表无边界。

复杂度

• 时间复杂度：$O(n)$，每个节点恰好访问一次；
• 空间复杂度：$O(n)$，递归栈深度最坏为树高（退化为链表时）。

三、BFS 解法：用队列逐层校验

思路

区间约束的思想与 DFS 完全相同，区别在于用队列代替递归栈，逐层（level by level）出队校验：

1. 树为空直接返回true；
2. 将(root, -∞, +∞)入队；
3. 循环直到队列为空：弹出(node, leftBound, rightBound)，若node.val不在(leftBound, rightBound)内则返回false；左孩子以(leftBound, node.val)入队，右孩子以(node.val, rightBound)入队；
4. 全部通过则返回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: Option<Rc<RefCell<TreeNode>>>) -> 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永远不成立，导致误判。解决方案有三种，仓库均有对应实现：

六、多语言对照与仓库索引

本仓库为本题提供了 13 种语言的完整实现，除上文引用外还包括：

• c/0098-validate-binary-search-tree.c
• csharp/0098-validate-binary-search-tree.cs
• javascript/0098-validate-binary-search-tree.js
• kotlin/0098-validate-binary-search-tree.kt
• swift/0098-validate-binary-search-tree.swift

阅读这些实现时建议对照 完整题解文章 中的分步算法说明，观察同一算法在不同语言里如何处理边界类型与空值语义。

总结

验证二叉搜索树的核心方法论可以浓缩为三点：

1. 约束必须来自全部祖先，不能只看父节点；
2. 区间传递是 $O(n)$ 解法（DFS 或 BFS）的统一骨架——向下走时用当前节点值收紧一侧边界；
3. 边界表示要防溢出：用更宽的类型（long）或可空类型（null）表示无穷。

掌握区间约束法后，你不仅能通过本题，还能自然迁移到 最大 BST 子树 等衍生问题——后者正是基于"子树是否满足区间约束"这一思想的直接延伸。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode