最近在刷 LeetCode hot100做到第 98 题《验证二叉搜索树》这道题可以说是我在二叉树专题里翻车次数最多的一道题。第一次写的时候觉得很简单结果提交了五次都没过第二次刷觉得自己懂了换成中序遍历又踩了边界条件的坑第三次刷才算把递归、迭代、中序遍历三种写法彻底打通。今天干脆把这道题从思路到代码到坑点完整梳理一遍给同样卡在这道题上的朋友做个参考。如果你正在刷 LeetCode 的 hot100 列表或者刚开始系统练二叉树的题目这道题很适合作为“二叉搜索树”专题的入门题。它考的是最基本的 BST 性质但把边界条件、递归传参、中序遍历逻辑全部串起来了。刷完这道题你再去做“二叉搜索树迭代器”“恢复二叉搜索树”这一类的题会顺很多。1. 题目到底在考什么二叉搜索树的严格定义1.1 不是“左小右大”这么简单LeetCode 98 的题目描述很简洁给你一个二叉树的根节点判断它是否是一个有效的二叉搜索树BST。官方定义有三条节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身也必须是二叉搜索树。很多新手包括我当年看到这个定义第一反应是写一个递归判断左孩子是否小于根、右孩子是否大于根然后递归向下检查。这个方向是对的但只做一半。因为二叉搜索树的约束是“全局”的不是“局部”的。举个例子你就明白了5 / \ 4 6 / \ 3 7只看局部6 的右孩子是 77 6没问题6 的左孩子是 33 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 一直是 53 一进来就发现 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 中会得到什么先序遍历根 - 左 - 右数组中的每个数都大于其子树中的所有数不确定别用中序遍历左 - 根 - 右严格递增序列后序遍历左 - 右 - 根序列不是直观递增但可以用于判断 BST 的某些变体如子树大小问题如果你在别的题里听到“先序、中序、后序怎么确定”核心逻辑就是看根节点在什么时候被访问。根在第一个就是先序根在中间就是中序根在最后就是后序。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 wrapperNode.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 用一份简单的测试用例表自测提交之前建议你至少跑这几个用例用例期望结果说明[]空树true空树特判[1]单节点true边界值[2,1,3]true标准 BST[5,1,4,null,null,3,6]false右子树出现比根小的值[5,4,6,null,null,3,7]false局部有序但全局无序[2147483647]true测试 int 边界[-2147483648]true测试 int 边界把这三个思路都写完再把测试用例表跑一遍基本就可以放心提交了。5.6 如何快速在本地调试建树如果你习惯在本地 IDE 里跑 LeetCode 的树需要写一个根据层序遍历数组建树的辅助函数。这里给一个简单的 Python 版本class TreeNode: def __init__(self, val0, leftNone, rightNone): 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 相关的题目时先在草稿纸上画一棵树给它的节点标上值然后手动做一次中序遍历把得到的序列写出来。如果这个序列不是严格递增的就说明这棵树有问题。用这个“纸上验证”的方法去理解题目比空想代码要快得多。
LeetCode 98验证二叉搜索树：三种解法与边界坑点实战解析
最近在刷 LeetCode hot100做到第 98 题《验证二叉搜索树》这道题可以说是我在二叉树专题里翻车次数最多的一道题。第一次写的时候觉得很简单结果提交了五次都没过第二次刷觉得自己懂了换成中序遍历又踩了边界条件的坑第三次刷才算把递归、迭代、中序遍历三种写法彻底打通。今天干脆把这道题从思路到代码到坑点完整梳理一遍给同样卡在这道题上的朋友做个参考。如果你正在刷 LeetCode 的 hot100 列表或者刚开始系统练二叉树的题目这道题很适合作为“二叉搜索树”专题的入门题。它考的是最基本的 BST 性质但把边界条件、递归传参、中序遍历逻辑全部串起来了。刷完这道题你再去做“二叉搜索树迭代器”“恢复二叉搜索树”这一类的题会顺很多。1. 题目到底在考什么二叉搜索树的严格定义1.1 不是“左小右大”这么简单LeetCode 98 的题目描述很简洁给你一个二叉树的根节点判断它是否是一个有效的二叉搜索树BST。官方定义有三条节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身也必须是二叉搜索树。很多新手包括我当年看到这个定义第一反应是写一个递归判断左孩子是否小于根、右孩子是否大于根然后递归向下检查。这个方向是对的但只做一半。因为二叉搜索树的约束是“全局”的不是“局部”的。举个例子你就明白了5 / \ 4 6 / \ 3 7只看局部6 的右孩子是 77 6没问题6 的左孩子是 33 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 一直是 53 一进来就发现 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 中会得到什么先序遍历根 - 左 - 右数组中的每个数都大于其子树中的所有数不确定别用中序遍历左 - 根 - 右严格递增序列后序遍历左 - 右 - 根序列不是直观递增但可以用于判断 BST 的某些变体如子树大小问题如果你在别的题里听到“先序、中序、后序怎么确定”核心逻辑就是看根节点在什么时候被访问。根在第一个就是先序根在中间就是中序根在最后就是后序。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 wrapperNode.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 用一份简单的测试用例表自测提交之前建议你至少跑这几个用例用例期望结果说明[]空树true空树特判[1]单节点true边界值[2,1,3]true标准 BST[5,1,4,null,null,3,6]false右子树出现比根小的值[5,4,6,null,null,3,7]false局部有序但全局无序[2147483647]true测试 int 边界[-2147483648]true测试 int 边界把这三个思路都写完再把测试用例表跑一遍基本就可以放心提交了。5.6 如何快速在本地调试建树如果你习惯在本地 IDE 里跑 LeetCode 的树需要写一个根据层序遍历数组建树的辅助函数。这里给一个简单的 Python 版本class TreeNode: def __init__(self, val0, leftNone, rightNone): 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 相关的题目时先在草稿纸上画一棵树给它的节点标上值然后手动做一次中序遍历把得到的序列写出来。如果这个序列不是严格递增的就说明这棵树有问题。用这个“纸上验证”的方法去理解题目比空想代码要快得多。
