企业官网建设流程全解析

最近在刷 LeetCode hot100，做到第 98 题《验证二叉搜索树》，这道题可以说是我在二叉树专题里翻车次数最多的一道题。第一次写的时候觉得很简单，结果提交了五次都没过；第二次刷觉得自己懂了，换成中序遍历又踩了边界条件的坑；第三次刷才算把递归、迭代、中序遍历三种写法彻底打通。今天干脆把这道题从思路到代码到坑点完整梳理一遍，给同样卡在这道题上的朋友做个参考。

如果你正在刷 LeetCode 的 hot100 列表，或者刚开始系统练二叉树的题目，这道题很适合作为“二叉搜索树”专题的入门题。它考的是最基本的 BST 性质，但把边界条件、递归传参、中序遍历逻辑全部串起来了。刷完这道题，你再去做“二叉搜索树迭代器”“恢复二叉搜索树”这一类的题会顺很多。

1. 题目到底在考什么：二叉搜索树的严格定义

1.1 不是“左小右大”这么简单

LeetCode 98 的题目描述很简洁：给你一个二叉树的根节点，判断它是否是一个有效的二叉搜索树（BST）。官方定义有三条：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身也必须是二叉搜索树。

很多新手（包括我当年）看到这个定义，第一反应是写一个递归：判断左孩子是否小于根、右孩子是否大于根，然后递归向下检查。这个方向是对的，但只做一半。因为二叉搜索树的约束是“全局”的，不是“局部”的。

举个例子你就明白了：

5 / \ 4 6 / \ 3 7

只看局部，6 的右孩子是 7，7 > 6，没问题；6 的左孩子是 3，3 < 6，也没问题。但这棵树不是 BST，因为 3 在根节点 5 的右子树里，却比 5 小。这就是经典的“局部有序，全局无序”。

1.2 用一个日常场景帮助理解

你可以把 BST 想象成一个严格有序的队列：每个人都站在自己的位置上，左边的人必须比自己“小”，右边的人必须比自己“大”。但这个“大小”不是只跟旁边的人比，而是跟这条队伍里所有站在他前面的人比。一个位置如果出现在某个人的右子树里，那它必须大于这个人的所有祖先；如果出现在左子树里，就必须小于所有祖先。

所以，这道题考察的本质上是一个“祖先约束”的问题。你在递归的时候不能只传当前节点，还必须把当前节点允许取值的上下界一路传下去。这也是整道题的核心思路。

1.3 复杂度预期

这种树上的遍历题，最优解的时间复杂度基本就是 O(n)，n 是节点数，因为每个节点至少要访问一次。空间复杂度取决于递归深度，最坏情况是链状树，递归深度为 n，所以空间是 O(n)；平均情况（平衡树）是 O(log n)。

LeetCode 的输入范围里，节点 val 可能很大，也可能很小，这里其实埋了一个很深的坑，后面专门开一节讲。

2. 解法一：递归传上下界，最稳的“正规军”思路

2.1 核心思路：每个节点都要活在“允许范围”里

既然局部比较不够，那我们就在递归的时候给每个节点限定一个取值范围（low, high）。如果当前节点的值不在这个范围内，直接返回 false；否则继续往左子树和右子树递归。

关键在于更新范围的方式：

• 递归检查左子树时，范围变成 (low, 当前节点值)，因为左子树里的所有值都必须小于当前节点。
• 递归检查右子树时，范围变成 (当前节点值, high)，因为右子树里的所有值都必须大于当前节点。

初始调用时，根节点的范围是负无穷到正无穷，也就是没有任何限制。我们用 Python 的 float('-inf') 和 float('inf') 表示，或者用 None 做特殊判断。

2.2 递归代码参考

def isValidBST(root): def helper(node, low, high): if not node: return True if node.val <= low or node.val >= high: return False return helper(node.left, low, node.val) and helper(node.right, node.val, high) return helper(root, float('-inf'), float('inf'))

这段代码非常短，但如果你没想明白 low 和 high 的作用，很容易漏掉右子树里比根还小的数。这是这道题最推荐的写法，面试的时候也最容易讲清楚。

2.3 为什么左子树只需要改 high，右子树只需要改 low

我刚开始学的时候一直纠结一个问题：检查左子树的时候，low 为什么不用变？答案是，左子树里所有的节点不仅要小于当前节点，还必须大于从祖先传下来的 low。比如根节点是 10，根的左子树里某个右孩子是 8，它大于自己的父节点 5，但小于 10，所以它其实是合法的。如果左子树递归时把 low 丢了，只检查“小于父节点”这一条，就可能把不合法的数放进来。

反过来，如果只比较局部，像那个 [5, 4, 6, null, null, 3, 7] 用例，3 在 5 的右子树里，比 5 小，而递归右子树时 low 一直是 5，3 一进来就发现 3 <= 5，直接返回 false。

这里还有一个细节：题目要求是严格小于、严格大于，所以判断条件里用了 <= 和 >=。如果题目改成允许相等，那判断条件就要换成 < 和 >，同时更新边界时也要注意等号。

2.4 复杂度分析

时间上每个节点访问一次，O(n)。空间上递归栈最大深度等于树高，平均 O(log n)，最坏 O(n)。如果面试官追问还记不记得空间复杂度，你可以补一句：链状树会退化到 O(n)，所以工程上如果树很深，递归有爆栈风险，这时候可以换成显式栈的迭代写法。

3. 解法二：中序遍历递增，利用 BST 的“隐藏性质”

3.1 BST 中序遍历的规律

先复习一个知识点：对一棵二叉搜索树做中序遍历（左、根、右），得到的序列一定是严格递增的。这个结论反过来也成立：如果一棵树的中序遍历结果是严格递增的，那它就是 BST。

这个性质非常关键，很多二叉搜索树的题目都会用到。比如“二叉搜索树中第 K 小的元素”“恢复二叉搜索树”，本质都是在“中序遍历”上做文章。所以刷这道题的时候，建议把中序遍历也彻底掌握。

判断方法很简单：用中序遍历访问树里的每个节点，并记录前一个访问的节点值。如果当前节点值不大于前一个节点值，说明不满足严格递增，返回 false。

3.2 递归中序遍历的代码

def isValidBST(root): prev = None def dfs(node): nonlocal prev if not node: return True if not dfs(node.left): return False if prev is not None and prev >= node.val: return False prev = node.val return dfs(node.right) return dfs(root)

这里有一个特别容易踩的坑：在 Python 里，如果直接在函数内给 prev 赋值，Python 会把它当成局部变量，导致报错或者逻辑错乱。所以要么用 nonlocal 声明，要么把 prev 放到一个长度为 1 的列表里，例如 prev = [None]，然后在代码里用 prev[0]。我第一次写的时候没加 nonlocal，代码直接报 UnboundLocalError，排查了好一会儿。

3.3 迭代中序遍历，不依赖递归栈

很多 LeetCode 题解还会给你一个迭代版本，用显式栈模拟递归。这样做的好处是空间开销理论上可以控制，不容易因为树太高导致函数调用栈溢出。考试和实际工程中，如果树的深度可能上万层，递归版本不一定安全。

def isValidBST(root): stack = [] prev = None cur = root while stack or cur: while cur: stack.append(cur) cur = cur.left cur = stack.pop() if prev is not None and prev >= cur.val: return False prev = cur.val cur = cur.right return True

这段代码的模板要背熟，它是一个通用的中序遍历框架。左边的 while 负责把左子树压栈，中间的 pop 负责处理根节点，最后的 cur = cur.right 转向右子树。只要能熟练默写这个框架，后面做其他中序相关题目会快很多。

3.4 对比一下三种常见遍历方式

二叉树的遍历顺序经常有朋友搞混，这里顺手整理一下：

如果你在别的题里听到“先序、中序、后序怎么确定”，核心逻辑就是看根节点在什么时候被访问。根在第一个就是先序，根在中间就是中序，根在最后就是后序。BST 判断里最常用的是中序，因为它的输出天然有序。

4. 解法三：迭代上下界，递归版本的“无栈化”改造

4.1 把递归函数改成显式栈

前面讲的递归传上下界版本，本质上是一个深度优先搜索。如果递归深度太深，可以把每个节点的 (node, low, high) 三元组放到显式栈里。每次从栈里弹出一个节点，判断它的值是否在范围内，然后把它的左右孩子连同新的范围一起压栈。

def isValidBST(root): if not root: return True stack = [(root, float('-inf'), float('inf'))] while stack: node, low, high = stack.pop() if node.val <= low or node.val >= high: return False if node.left: stack.append((node.left, low, node.val)) if node.right: stack.append((node.right, node.val, high)) return True

这个版本的好处是不用递归，逻辑清晰，而且空间复杂度不受递归调用栈的影响。当然，因为要存三元组，实际内存比递归版本稍大一点，但可控。

4.2 Morris 遍历，空间 O(1) 的进阶方案

如果你还想更进一步，可以了解 Morris 中序遍历。它的思路是利用树中空闲的右指针构造临时线索，遍历完再恢复树的原状。这样可以把空间复杂度降到 O(1)，很适合内存受限的场景，比如嵌入式环境、老式面试官追问“能不能用 O(1) 空间实现”。

Morris 的代码相对复杂，这里不给完整实现了，只提供一个思维框架。简单说，在遍历到一个节点时，先找到它左子树中“最右侧”的节点，把这个节点的右指针临时指向当前节点，然后去遍历左子树；当再次回到当前节点时，说明左子树已经处理完，再把临时线索拆掉，转向右子树。这个操作听起来绕，但多画几遍图就能理解。

不过说实话，绝大多数面试场景不会要求你手写 Morris，能讲出思路已经够用了。日常刷题，优先掌握递归版本和迭代栈版本就可以。

5. 这几个坑我每次刷都会踩，建议你直接避开

5.1 int 边界才是最大的隐藏 Boss

这道题 LeetCode 官方给出的测试用例里，节点值可能是 INT_MIN 或者 INT_MAX。这意味着，如果你初始上下界用 Integer.MIN_VALUE 和 Integer.MAX_VALUE，就可能出问题。

举个例子，一棵只有一个节点的树，节点值正好是 -2147483648（即 INT_MIN）。递归版本的初始 low 如果用 Integer.MIN_VALUE，那么判断条件 node.val <= low 就会变成 -2147483648 <= -2147483648，结果为 true，直接返回 false。但一棵只有根节点的树显然是一个合法的 BST，于是你就 WA 了。

解决办法很简单：

• 在 Python 里用 float('-inf') 和 float('inf')，因为整数和浮点数可以直接比较。
• 在 C++ 或 Java 里用 long 类型，初始化为 LONG_MIN 和 LONG_MAX，或者用 optional wrapper，Node.val 不可能超出 long 的范围。
• 也可以用 None 代表无边界，在比较前判断一下。

这个坑我在第一次刷的时候花了十来分钟才定位到。所以写递归传边界的时候，初始值的类型一定要想清楚，别偷懒直接用了 int 的最小最大值。

5.2 等号问题：BST 允许重复值吗

LeetCode 的这道题默认 BST 是严格递增的，也就是“小于”和“大于”，不允许等于。所以判断条件用 <= 和 >=。

但如果你看过一些资料或者刷过某些变体题，会发现有的题定义 BST 允许左子树小于等于当前节点。这种变体在做题时非常容易混淆。我的建议是，看到题目先看描述，不要凭记忆去猜。LeetCode 98 的标准答案是严格版，你代码里用了 <= 就不会错。

5.3 空树到底算不算 BST

题目默认空树也是一棵有效的二叉搜索树。这个在数学上空集满足全称命题，所以返回 true。如果你在代码里特判了空树返回 false，又会多一个 WA。很多新手在这上面丢过分，我也丢过。

5.4 只比较左右孩子是最大的思维误区

前面已经说了 [5, 4, 6, null, null, 3, 7] 这个例子。我把它写在前面，就是提醒各位，写代码前先在纸上画一棵树，故意构造一个“右子树的左孩子比根小”的情况，看你自己的递归能不能拦下来。如果拦不下来，说明你还只停留在局部比较，没有把祖先范围传下去。

5.5 用一份简单的测试用例表自测

提交之前，建议你至少跑这几个用例：

把这三个思路都写完，再把测试用例表跑一遍，基本就可以放心提交了。

5.6 如何快速在本地调试建树

如果你习惯在本地 IDE 里跑 LeetCode 的树，需要写一个根据层序遍历数组建树的辅助函数。这里给一个简单的 Python 版本：

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def build_tree(values): if not values: return None root = TreeNode(values[0]) nodes = [root] i = 1 while i < len(values): node = nodes.pop(0) if values[i] is not None: node.left = TreeNode(values[i]) nodes.append(node.left) i += 1 if i < len(values) and values[i] is not None: node.right = TreeNode(values[i]) nodes.append(node.right) i += 1 return root

注意 values 里用 None 表示空节点，这个辅助函数能帮你快速构造测试样例。调试递归函数时，我习惯先打印一下前几个节点的访问顺序，确认自己的遍历逻辑没问题。

6. 刷完这道题后，我的一点心得体会

我个人刷这道题最大的收获，不是记住了三种解法，而是理解了“递归传参的本质”。当你需要在递归过程中保留“祖先信息”的时候，直接在参数列表里加两个边界，比全局变量、哈希表那些方式要干净得多。这个思路在“判断二叉树是否对称”“路径总和”这些题里也很常见。

如果你现在还在刷 hot100 的早期阶段，这道题建议多写几遍，直到你能闭着眼睛写出递归上下界版本和中序遍历版本。第一遍可以直接看题解，但第二遍一定要逼自己不看任何资料，从空白的编辑器开始写。写完之后，再把第 94 题（二叉树的中序遍历）、第 230 题（BST 中第 K 小的元素）一起刷了，这几道题的底层逻辑是高度重合的。

最后分享一个小技巧：做 BST 相关的题目时，先在草稿纸上画一棵树，给它的节点标上值，然后手动做一次中序遍历，把得到的序列写出来。如果这个序列不是严格递增的，就说明这棵树有问题。用这个“纸上验证”的方法去理解题目，比空想代码要快得多。