力扣 98“验证二叉搜索树”是我在技术面试里最常拿来考人的一道树题。这道题看起来门槛不高二叉搜索树的定义一句话就能说完代码量也不大可真正能在五分钟内写对、并且把边界条件讲清楚的人其实不多。你去看它的提交通过率常年只有三分之一左右作为一道标记为中等偏简单的题目这个数据相当扎眼。这道题要求判断一棵二叉树是不是“合法”的二叉搜索树。难点不在语法而在定义本身左子树只包含小于当前节点的键右子树只包含大于当前节点的键并且左、右子树本身也必须是二叉搜索树。这里藏着好几个让人“想当然”的坑。我见过太多候选人写出“只比较 root 和直接孩子”的代码跑示例用例没问题一提交就挂。这篇文章按我自己的刷题习惯来写先拆解有哪些常见的错误直觉再给出三种核心解法——中序遍历、上下界递归、显式栈迭代然后用一组覆盖极端情况的用例把解法验证一遍最后聊聊面试追问和工程上的延伸。读完你应该不仅能自己写对还能在面试现场把思路完整讲清楚。1. 为什么这么多人在力扣98上翻车三个隐藏陷阱1.1 局部有序不等于全局有序很多人的第一反应是递归检查每个节点左孩子小于父节点右孩子大于父节点然后递归继续检查孩子。这个思路错得很典型。它只保证了“局部”满足大小关系却忽略了祖先节点对整个子树的约束。比如这样一棵树10 / \ 5 15 / \ 6 20用“只比较父子”的代码去判断5 10 通过15 10 通过6 15 通过20 15 通过最终会返回 true。但这棵树并不是合法的二叉搜索树因为 6 在根节点 10 的右子树里却比 10 小。二叉搜索树是一个“全局有序”的结构。每个节点不仅要比直接父节点大或小还要比整条路径上的所有祖先都满足约束。一句话解释在中序遍历下BST 必须产生一个严格递增的序列。这也是我们后面第一种解法的根基。1.2 值相等到底算不算合法先看二叉树搜索树的严格定义左子树所有键小于根节点右子树所有键大于根节点。关键词是“小于”和“大于”没有“等于”。这意味着值重复的树不算合法 BST。例如根节点是 2左孩子是 2虽然常见教科书里有时允许“左子节点小于等于父节点”但力扣 98 的官方定义是按严格不等来判定的。于是判断条件要用和来拦截而不是和。很多人在这个细节上出错是因为他们平时实现二分搜索树时习惯了left root right这种版本。所以我在开写之前都会先确认一下题目约定力扣 98 的标准是“左小右大严格不等”。如果你自己造数据结构为了处理重复值可能改成左小右大于等于但那是另一套规则不能混用到这里。1.3 边界初值和整数溢出问题这是最容易被忽略、也最容易在看了提交报错后一脸懵的坑。如果我们用“上下界法”来解需要给根节点一个合法区间负无穷到正无穷。在 Python 里没问题直接用float(-inf)和float(inf)就行。但在 Java 这类强类型语言里节点值是int类型最自然的想法是用Integer.MIN_VALUE和Integer.MAX_VALUE作为初始边界。问题来了如果树里恰好有一个节点的值是Integer.MIN_VALUE它作为右边界或左边界时判定条件node.val low会如何把这个值和初始下界Integer.MIN_VALUE比较会出现“等于下界”于是被错误地判为不合法。单节点树[ -2147483648 ]本来应该返回 true却可能返回 false。正确的做法有两种一种是用Long.MIN_VALUE和Long.MAX_VALUE作为初始边界因为int的取值范围完整落在long内另一种用null来表示“没有边界”每次判断前先检查边界是否存在。我在后面的代码里两种都会给出。2. 解法一中序遍历性质BST天然有序的底层逻辑2.1 为什么中序递增是充要条件二叉搜索树有一个特别优美的性质对它进行中序遍历左子树、根节点、右子树得到的序列一定是严格递增的。反过来也成立如果一棵二叉树的中序遍历结果是严格递增的它一定是一棵合法的二叉搜索树。可以这样理解在中序遍历里某个节点的左子树全部排在它前面右子树全部排在它后面。既然序列严格递增那就自动满足“左子树所有值 根 右子树所有值”。递归地看整棵树也就处处满足 BST 的定义。所以“验证 BST”这个看似复杂的递归问题可以部分转化成“验证遍历序列的单调性”。我们用递归做中序遍历维护一个prev变量记录上一个被访问的节点每当访问一个新节点时检查它是否大于prev的值。2.2 递归代码用 prev 记录前一个节点# Python 3 class Solution: def isValidBST(self, root: TreeNode) - bool: prev None def dfs(node): nonlocal prev if node is None: return True # 左子树不合法直接返回 False if not dfs(node.left): return False # 当前节点必须严格大于上一个节点 if prev is not None and prev.val node.val: return False prev node # 右子树不合法直接返回 False return dfs(node.right) return dfs(root)这里的prev必须保存完整节点还是只保存值其实都行保存节点是为了程序语义更清楚。真正核心的是比较prev.val node.val时用到了大于等于这样才能拦截相等的情况。另外注意nonlocal prev这个声明。Python 里如果在嵌套函数中给外层变量重新赋值必须声明nonlocal否则会报错。这点在白板写代码时很容易疏忽建议面试前专门记一下。2.3 提前返回的细节不是所有递归都要等到最后有人会把这个题写成先完整跑完中序遍历把值放进一个数组再判断数组是否递增。逻辑更直白但会多一次 O(n) 的额外存储而且在发现第一个逆序之后还会继续访问后面无用的节点。更好的做法是在递归过程中发现违反递增时立刻返回 false。上面代码里左子树返回 false 后not dfs(node.left)直接短路返回处理完当前节点发现prev.val node.val也是立刻返回 false。这样既节省时间也让代码意图更明显。有人会问既然 BST 中序一定递增那能不能只检查相邻两个节点之间的大小可以这就是中序解法的本质。但要注意“相邻节点”不是二叉树里的父子相邻而是中序访问顺序上的相邻所以必须靠遍历去维护。3. 解法二上下界下推法给每个节点划定合法区间3.1 核心思想每个节点都有一个“合法区间”中序遍历是把 BST 的“有序性”当成解题入口。另一种更直接的想法是递归过程中给每个节点传递它允许的取值范围。根节点没有约束所以范围是负无穷到正无穷。进入左子树时所有值都必须小于根节点所以把上界更新为根节点值下界保持父节点的下界。进入右子树时所有值都必须大于根节点所以把下界更新为根节点值上界保持父节点的上界。每个节点只需检查自己的值是否落在当前范围内然后带着新范围递归到左右孩子。这个解法不容易写错因为它把约束蕴含在参数里而不是依靠“已经访问过哪些节点”的记忆。3.2 代码Java 用 LongPython 用 None// Java class Solution { public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long low, long high) { if (node null) { return true; } if (node.val low || node.val high) { return false; } return validate(node.left, low, node.val) validate(node.right, node.val, high); } }Java 里节点值是int但方法参数声明成long所以初始边界用Long.MIN_VALUE/Long.MAX_VALUE就能完整包住所有整数避免边界相等造成误判。Python 版本我用None表示无穷边界避免浮点数和整数之间的比较# Python 3 class Solution: def isValidBST(self, root: TreeNode) - bool: def dfs(node, low, high): if node is None: return True if low is not None and node.val low: return False if high is not None and node.val high: return False return dfs(node.left, low, node.val) and dfs(node.right, node.val, high) return dfs(root, None, None)用None的好处是语义清晰low为 None 表示下界不存在左子树什么样的最小值都可以接受。这也规避了float(-inf)和int比较时可能带来的理解成本。3.3 上下界法为什么比中序遍历更“早停”中序遍历要等一部分节点被处理之后才能确定是否存在逆序。上下界法则是在进入子树前就判断这个子树是否可能合法一旦某个节点超出范围立即返回 false不需要遍历完整棵树。最坏复杂度仍然都是 O(n)但平均情况上下界法往往能更早剪枝。另外它的证明也直观如果每个节点的值都在从根到它的路径所决定的区间内等价于这个树所有节点的值都满足 BST 的递归定义。我个人在做白板题时更愿意先用这个解法因为它不需要记忆上一轮状态也不容易漏掉“全局约束”。4. 解法三显式栈迭代把递归翻译成“现场模拟”4.1 为什么要会迭代版本递归代码简洁但工程环境里并不是总能用递归。极端情况下二叉树退化成链表递归深度达到 n栈溢出风险很高。面试官也喜欢追问“你能不能不用递归写”。所以至少掌握一种迭代版本是很有必要的。这里有两种思路可以选一是用显式栈模拟中序遍历二是用显式栈模拟上下界下推。两者都可以在力扣上通过我建议根据自己的思维习惯至少掌握一个。4.2 迭代中序遍历左链压栈弹出检测// Java class Solution { public boolean isValidBST(TreeNode root) { DequeTreeNode stack new ArrayDeque(); TreeNode cur root; TreeNode prev null; while (cur ! null || !stack.isEmpty()) { // 一路向左压栈 while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); // 中序访问当前节点 if (prev ! null prev.val cur.val) { return false; } prev cur; // 转向右子树 cur cur.right; } return true; } }这个版本的执行过程可以想象成“模拟递归栈”先把左子树整条路径压进去弹出一个节点时处理它然后转向右子树重复这个过程。prev的作用和递归版一样记录中序访问顺序的上一个节点。用ArrayDeque还是Stack在 Java 里优先用ArrayDeque虽然名字里带 Deque但作为栈使用时性能更好也不会像旧版Stack那样带锁。LeetCode 环境两种都能过但面试时说出这个区别会显得你关注底层实现。4.3 迭代上下界两个栈同步维护节点和范围这种方法更直观一点也更少见适合作为亮点讲给面试官// Java class Solution { public boolean isValidBST(TreeNode root) { DequeTreeNode nodeStack new ArrayDeque(); Dequelong[] boundStack new ArrayDeque(); if (root ! null) { nodeStack.push(root); boundStack.push(new long[]{Long.MIN_VALUE, Long.MAX_VALUE}); } while (!nodeStack.isEmpty()) { TreeNode node nodeStack.pop(); long[] bound boundStack.pop(); if (node.val bound[0] || node.val bound[1]) { return false; } if (node.right ! null) { nodeStack.push(node.right); boundStack.push(new long[]{node.val, bound[1]}); } if (node.left ! null) { nodeStack.push(node.left); boundStack.push(new long[]{bound[0], node.val}); } } return true; } }两个栈分别存“待处理的节点”和“该节点对应的合法区间”。入栈顺序没有硬性要求反正每次弹出都会检查。这个版本的空间复杂度可能略高一点因为它要额外保存一个数组但思路不容易绕晕。如果面试官要你只用一个栈那我还是推荐迭代中序如果对方更看重“你是否理解上下界约束”那双向栈方案能直接体现你的思路。5. 测试用例表从简单到刁钻验证解法的闭环5.1 用表格梳理关键用例刷题只写代码不测边界等于白刷。我把自己在力扣 98 上反复用的一组用例整理成了表格。这里的输入按力扣的层序遍历数组表示null表示空缺节点。输入数组期望能发现的坑[2,1,3]true最基本的合法树所有解法都该通过[5,1,4,null,null,3,6]false只要一根右子树里的节点小于根节点整棵树就不合法[10,5,15,null,null,6,20]false只比较父子节点会误判6 在 15 左子树里却小于根节点 10[2,2,2]false重复值不会被严格大于/小于的规则放行[-2147483648]true节点值等于 Integer.MIN_VALUE初值不当会误判[2147483647, -2147483648]true根最大左孩子最小合法边界成对出现[]true空树在很多实现里被认为是 BST拿这些用例去跑你写的解法能过滤掉绝大部分隐藏 bug。特别是那一组和Integer.MIN_VALUE有关的用例最容易被忽略。5.2 空树到底算不算二叉搜索树力扣 98 的期望输出里空树返回 true。理由通常解释为“空树满足所有属性的前提条件”也就是数学里的“空真”概念。如果你在实际业务中校验配置树空树返回 true 也符合直觉没有违反约束的节点。不过面试时应该主动和面试官确认这个约定因为有些领域定义会要求 BST 至少有一个节点。你主动提这个边界本身就是加分项。5.3 如何快速自测你的解法我有个习惯在写核心递归函数之前先在纸上画出三个例子——一个合法树、一个右子树里混入小节点的树、一个左子树里混入大节点的树。然后手动模拟一遍递归的传播过程。比如对[10,5,15,null,null,6,20]用上下界法走到 6 时它的边界来自根节点 10 和父节点 15合法区间是 (10, 15)。6 不在这个区间里直接 false。这样一推代码逻辑就清晰了。不要一上来就编译提交先手动推两三个反例能帮你省下很多提交失败的时间。6. 面试追问与工程落地BST校验不止存在于“刷题”6.1 面试官最常见的一套追问组合力扣 98 这类题面试官很少只满足于“你写对了”。我作为面试官时通常会按这个顺序往下问先讲正确性为什么你的解法能判定所有情况你会怎么证明再问复杂度时间复杂度和空间复杂度各是多少递归调用栈的深度由什么决定然后要求换解法别用递归迭代怎么写别用中序上下界怎么写最后可能加变化如果允许重复值你想用“左小右大于等于”还是“左小右大”的规则改动哪里这些追问的目的不是刁难而是考察你对 BST 定义、递归展开过程和边界条件是否真的有把握。所以刷题时不要背代码要把“为什么这个条件是充分的”想清楚。至于证明可以用归纳法对于上下界解法递归调用前所有祖先已经给当前节点限定了区间节点值只要在区间内并且递归地满足左、右子树的区间约束整棵子树就合法。这样讲逻辑链就完整了。6.2 工程里哪里会用到“验证BST”离开力扣BST 验证也不是纸上谈兵。数据库里的 B-Tree/BTree 虽然不是严格的二叉树但在节点分裂和合并时会做大量有序性校验内存中的红黑树、AVL 树本质也是 BST 加上平衡条件插入删除后如果有序性被破坏整个查找结构就废了。做配置系统的人也会遇到类似场景配置项本身是一个树形结构不同路径下的 key 应该满足某种大小关系校验函数和isValidBST的思路几乎一样。规则引擎、权限树、甚至文件系统的目录排序都能找到 BST 校验的影子。所以这题的解题思路不是孤立的小技巧而是“递归定义 边界传播 遍历顺序”三个基础思维的组合体。这也是为什么大厂面试喜欢考它的原因。6.3 和它直接相关的变体题力扣 98 是很多树形题的“地基”。做明白它之后再看下面这些题会轻松很多力扣 99恢复二叉搜索树。核心就是用中序遍历找到两个位置错误的节点再用交换修复。力扣 230二叉搜索树中第 K 小的元素。中序遍历到第 K 个就是答案。力扣 530 / 783二叉搜索树的最小绝对差。中序遍历后比较相邻差值即可。力扣 98 的扩展场景验证一棵树是否平衡、是否完全二叉树虽然判断标准不同但“遍历 状态维护”的框架是类似的。刷完 98 再去做 99你会发现前者的prev记录技巧在后者错误节点检测里直接复用。这种“一题带一题”的学习方式比单纯堆题量效率高很多。7. 我的个人刷题习惯以及这次留下的几个提醒7.1 先把递归函数往上“屏”住再写主逻辑我刷这题时有个小经验不要先写isValidBST主函数而是先把递归函数dfs/validate的“职责”用一句话说清楚。比如“这个函数判断以 node 为根的子树是否合法并且所有节点值都在 (low, high) 内”。一旦职责明确了边界条件和递归调用就是顺手的事。如果是中序遍历法心里的口头禅是“上一节点不能大于等于当前节点”。把这句口诀放进去代码基本不会写错。7.2 提交失败时先打印中序序列如果你写的版本是收集数组再判断调试时可以先把中序序列打出来看一眼。看到[1, 3, 2]这种序列你能立刻想到只需要检查相邻逆序。看到[1, 1, 2]能意识到重复值被放行了。序列化输出比盯着树形图画半天更直观。我见过不少人提交失败后第一反应是改代码而不是看失败的输入用例。实际上力扣会给出具体树把它转成层序数组对照我上面那张用例表十有八九能定位到原因。7.3 这道题刷完之后最值得记住的三件事第一BST 的两个关键判定工具——中序递增和区间约束——是等价的面试时要能互相转换。第二严格的和加上可以用long或null处理的边界是这道题正确率的分水岭。第三递归、迭代两种形态都要能写因为代码只是思想的载体真正的思考发生在你画出树、推演区间的那十几秒里。最后说点题外话。我给别人讲这道题的时候经常建议他们先别看官方题解而是自己按“这个节点必须比我上一个大”和“这个节点必须在我祖先限定的范围内”两个方向各写一版。能把两个版本都写对并且说出为什么它们等价二叉搜索树的底层理解就真正到位了。很多年后你可能不记得这题代码的每个细节但这个“定义决定解法、解法又反哺定义”的过程会一直留在你的解题直觉里。
验证二叉搜索树：力扣98的三种解法与边界陷阱全解析
力扣 98“验证二叉搜索树”是我在技术面试里最常拿来考人的一道树题。这道题看起来门槛不高二叉搜索树的定义一句话就能说完代码量也不大可真正能在五分钟内写对、并且把边界条件讲清楚的人其实不多。你去看它的提交通过率常年只有三分之一左右作为一道标记为中等偏简单的题目这个数据相当扎眼。这道题要求判断一棵二叉树是不是“合法”的二叉搜索树。难点不在语法而在定义本身左子树只包含小于当前节点的键右子树只包含大于当前节点的键并且左、右子树本身也必须是二叉搜索树。这里藏着好几个让人“想当然”的坑。我见过太多候选人写出“只比较 root 和直接孩子”的代码跑示例用例没问题一提交就挂。这篇文章按我自己的刷题习惯来写先拆解有哪些常见的错误直觉再给出三种核心解法——中序遍历、上下界递归、显式栈迭代然后用一组覆盖极端情况的用例把解法验证一遍最后聊聊面试追问和工程上的延伸。读完你应该不仅能自己写对还能在面试现场把思路完整讲清楚。1. 为什么这么多人在力扣98上翻车三个隐藏陷阱1.1 局部有序不等于全局有序很多人的第一反应是递归检查每个节点左孩子小于父节点右孩子大于父节点然后递归继续检查孩子。这个思路错得很典型。它只保证了“局部”满足大小关系却忽略了祖先节点对整个子树的约束。比如这样一棵树10 / \ 5 15 / \ 6 20用“只比较父子”的代码去判断5 10 通过15 10 通过6 15 通过20 15 通过最终会返回 true。但这棵树并不是合法的二叉搜索树因为 6 在根节点 10 的右子树里却比 10 小。二叉搜索树是一个“全局有序”的结构。每个节点不仅要比直接父节点大或小还要比整条路径上的所有祖先都满足约束。一句话解释在中序遍历下BST 必须产生一个严格递增的序列。这也是我们后面第一种解法的根基。1.2 值相等到底算不算合法先看二叉树搜索树的严格定义左子树所有键小于根节点右子树所有键大于根节点。关键词是“小于”和“大于”没有“等于”。这意味着值重复的树不算合法 BST。例如根节点是 2左孩子是 2虽然常见教科书里有时允许“左子节点小于等于父节点”但力扣 98 的官方定义是按严格不等来判定的。于是判断条件要用和来拦截而不是和。很多人在这个细节上出错是因为他们平时实现二分搜索树时习惯了left root right这种版本。所以我在开写之前都会先确认一下题目约定力扣 98 的标准是“左小右大严格不等”。如果你自己造数据结构为了处理重复值可能改成左小右大于等于但那是另一套规则不能混用到这里。1.3 边界初值和整数溢出问题这是最容易被忽略、也最容易在看了提交报错后一脸懵的坑。如果我们用“上下界法”来解需要给根节点一个合法区间负无穷到正无穷。在 Python 里没问题直接用float(-inf)和float(inf)就行。但在 Java 这类强类型语言里节点值是int类型最自然的想法是用Integer.MIN_VALUE和Integer.MAX_VALUE作为初始边界。问题来了如果树里恰好有一个节点的值是Integer.MIN_VALUE它作为右边界或左边界时判定条件node.val low会如何把这个值和初始下界Integer.MIN_VALUE比较会出现“等于下界”于是被错误地判为不合法。单节点树[ -2147483648 ]本来应该返回 true却可能返回 false。正确的做法有两种一种是用Long.MIN_VALUE和Long.MAX_VALUE作为初始边界因为int的取值范围完整落在long内另一种用null来表示“没有边界”每次判断前先检查边界是否存在。我在后面的代码里两种都会给出。2. 解法一中序遍历性质BST天然有序的底层逻辑2.1 为什么中序递增是充要条件二叉搜索树有一个特别优美的性质对它进行中序遍历左子树、根节点、右子树得到的序列一定是严格递增的。反过来也成立如果一棵二叉树的中序遍历结果是严格递增的它一定是一棵合法的二叉搜索树。可以这样理解在中序遍历里某个节点的左子树全部排在它前面右子树全部排在它后面。既然序列严格递增那就自动满足“左子树所有值 根 右子树所有值”。递归地看整棵树也就处处满足 BST 的定义。所以“验证 BST”这个看似复杂的递归问题可以部分转化成“验证遍历序列的单调性”。我们用递归做中序遍历维护一个prev变量记录上一个被访问的节点每当访问一个新节点时检查它是否大于prev的值。2.2 递归代码用 prev 记录前一个节点# Python 3 class Solution: def isValidBST(self, root: TreeNode) - bool: prev None def dfs(node): nonlocal prev if node is None: return True # 左子树不合法直接返回 False if not dfs(node.left): return False # 当前节点必须严格大于上一个节点 if prev is not None and prev.val node.val: return False prev node # 右子树不合法直接返回 False return dfs(node.right) return dfs(root)这里的prev必须保存完整节点还是只保存值其实都行保存节点是为了程序语义更清楚。真正核心的是比较prev.val node.val时用到了大于等于这样才能拦截相等的情况。另外注意nonlocal prev这个声明。Python 里如果在嵌套函数中给外层变量重新赋值必须声明nonlocal否则会报错。这点在白板写代码时很容易疏忽建议面试前专门记一下。2.3 提前返回的细节不是所有递归都要等到最后有人会把这个题写成先完整跑完中序遍历把值放进一个数组再判断数组是否递增。逻辑更直白但会多一次 O(n) 的额外存储而且在发现第一个逆序之后还会继续访问后面无用的节点。更好的做法是在递归过程中发现违反递增时立刻返回 false。上面代码里左子树返回 false 后not dfs(node.left)直接短路返回处理完当前节点发现prev.val node.val也是立刻返回 false。这样既节省时间也让代码意图更明显。有人会问既然 BST 中序一定递增那能不能只检查相邻两个节点之间的大小可以这就是中序解法的本质。但要注意“相邻节点”不是二叉树里的父子相邻而是中序访问顺序上的相邻所以必须靠遍历去维护。3. 解法二上下界下推法给每个节点划定合法区间3.1 核心思想每个节点都有一个“合法区间”中序遍历是把 BST 的“有序性”当成解题入口。另一种更直接的想法是递归过程中给每个节点传递它允许的取值范围。根节点没有约束所以范围是负无穷到正无穷。进入左子树时所有值都必须小于根节点所以把上界更新为根节点值下界保持父节点的下界。进入右子树时所有值都必须大于根节点所以把下界更新为根节点值上界保持父节点的上界。每个节点只需检查自己的值是否落在当前范围内然后带着新范围递归到左右孩子。这个解法不容易写错因为它把约束蕴含在参数里而不是依靠“已经访问过哪些节点”的记忆。3.2 代码Java 用 LongPython 用 None// Java class Solution { public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long low, long high) { if (node null) { return true; } if (node.val low || node.val high) { return false; } return validate(node.left, low, node.val) validate(node.right, node.val, high); } }Java 里节点值是int但方法参数声明成long所以初始边界用Long.MIN_VALUE/Long.MAX_VALUE就能完整包住所有整数避免边界相等造成误判。Python 版本我用None表示无穷边界避免浮点数和整数之间的比较# Python 3 class Solution: def isValidBST(self, root: TreeNode) - bool: def dfs(node, low, high): if node is None: return True if low is not None and node.val low: return False if high is not None and node.val high: return False return dfs(node.left, low, node.val) and dfs(node.right, node.val, high) return dfs(root, None, None)用None的好处是语义清晰low为 None 表示下界不存在左子树什么样的最小值都可以接受。这也规避了float(-inf)和int比较时可能带来的理解成本。3.3 上下界法为什么比中序遍历更“早停”中序遍历要等一部分节点被处理之后才能确定是否存在逆序。上下界法则是在进入子树前就判断这个子树是否可能合法一旦某个节点超出范围立即返回 false不需要遍历完整棵树。最坏复杂度仍然都是 O(n)但平均情况上下界法往往能更早剪枝。另外它的证明也直观如果每个节点的值都在从根到它的路径所决定的区间内等价于这个树所有节点的值都满足 BST 的递归定义。我个人在做白板题时更愿意先用这个解法因为它不需要记忆上一轮状态也不容易漏掉“全局约束”。4. 解法三显式栈迭代把递归翻译成“现场模拟”4.1 为什么要会迭代版本递归代码简洁但工程环境里并不是总能用递归。极端情况下二叉树退化成链表递归深度达到 n栈溢出风险很高。面试官也喜欢追问“你能不能不用递归写”。所以至少掌握一种迭代版本是很有必要的。这里有两种思路可以选一是用显式栈模拟中序遍历二是用显式栈模拟上下界下推。两者都可以在力扣上通过我建议根据自己的思维习惯至少掌握一个。4.2 迭代中序遍历左链压栈弹出检测// Java class Solution { public boolean isValidBST(TreeNode root) { DequeTreeNode stack new ArrayDeque(); TreeNode cur root; TreeNode prev null; while (cur ! null || !stack.isEmpty()) { // 一路向左压栈 while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); // 中序访问当前节点 if (prev ! null prev.val cur.val) { return false; } prev cur; // 转向右子树 cur cur.right; } return true; } }这个版本的执行过程可以想象成“模拟递归栈”先把左子树整条路径压进去弹出一个节点时处理它然后转向右子树重复这个过程。prev的作用和递归版一样记录中序访问顺序的上一个节点。用ArrayDeque还是Stack在 Java 里优先用ArrayDeque虽然名字里带 Deque但作为栈使用时性能更好也不会像旧版Stack那样带锁。LeetCode 环境两种都能过但面试时说出这个区别会显得你关注底层实现。4.3 迭代上下界两个栈同步维护节点和范围这种方法更直观一点也更少见适合作为亮点讲给面试官// Java class Solution { public boolean isValidBST(TreeNode root) { DequeTreeNode nodeStack new ArrayDeque(); Dequelong[] boundStack new ArrayDeque(); if (root ! null) { nodeStack.push(root); boundStack.push(new long[]{Long.MIN_VALUE, Long.MAX_VALUE}); } while (!nodeStack.isEmpty()) { TreeNode node nodeStack.pop(); long[] bound boundStack.pop(); if (node.val bound[0] || node.val bound[1]) { return false; } if (node.right ! null) { nodeStack.push(node.right); boundStack.push(new long[]{node.val, bound[1]}); } if (node.left ! null) { nodeStack.push(node.left); boundStack.push(new long[]{bound[0], node.val}); } } return true; } }两个栈分别存“待处理的节点”和“该节点对应的合法区间”。入栈顺序没有硬性要求反正每次弹出都会检查。这个版本的空间复杂度可能略高一点因为它要额外保存一个数组但思路不容易绕晕。如果面试官要你只用一个栈那我还是推荐迭代中序如果对方更看重“你是否理解上下界约束”那双向栈方案能直接体现你的思路。5. 测试用例表从简单到刁钻验证解法的闭环5.1 用表格梳理关键用例刷题只写代码不测边界等于白刷。我把自己在力扣 98 上反复用的一组用例整理成了表格。这里的输入按力扣的层序遍历数组表示null表示空缺节点。输入数组期望能发现的坑[2,1,3]true最基本的合法树所有解法都该通过[5,1,4,null,null,3,6]false只要一根右子树里的节点小于根节点整棵树就不合法[10,5,15,null,null,6,20]false只比较父子节点会误判6 在 15 左子树里却小于根节点 10[2,2,2]false重复值不会被严格大于/小于的规则放行[-2147483648]true节点值等于 Integer.MIN_VALUE初值不当会误判[2147483647, -2147483648]true根最大左孩子最小合法边界成对出现[]true空树在很多实现里被认为是 BST拿这些用例去跑你写的解法能过滤掉绝大部分隐藏 bug。特别是那一组和Integer.MIN_VALUE有关的用例最容易被忽略。5.2 空树到底算不算二叉搜索树力扣 98 的期望输出里空树返回 true。理由通常解释为“空树满足所有属性的前提条件”也就是数学里的“空真”概念。如果你在实际业务中校验配置树空树返回 true 也符合直觉没有违反约束的节点。不过面试时应该主动和面试官确认这个约定因为有些领域定义会要求 BST 至少有一个节点。你主动提这个边界本身就是加分项。5.3 如何快速自测你的解法我有个习惯在写核心递归函数之前先在纸上画出三个例子——一个合法树、一个右子树里混入小节点的树、一个左子树里混入大节点的树。然后手动模拟一遍递归的传播过程。比如对[10,5,15,null,null,6,20]用上下界法走到 6 时它的边界来自根节点 10 和父节点 15合法区间是 (10, 15)。6 不在这个区间里直接 false。这样一推代码逻辑就清晰了。不要一上来就编译提交先手动推两三个反例能帮你省下很多提交失败的时间。6. 面试追问与工程落地BST校验不止存在于“刷题”6.1 面试官最常见的一套追问组合力扣 98 这类题面试官很少只满足于“你写对了”。我作为面试官时通常会按这个顺序往下问先讲正确性为什么你的解法能判定所有情况你会怎么证明再问复杂度时间复杂度和空间复杂度各是多少递归调用栈的深度由什么决定然后要求换解法别用递归迭代怎么写别用中序上下界怎么写最后可能加变化如果允许重复值你想用“左小右大于等于”还是“左小右大”的规则改动哪里这些追问的目的不是刁难而是考察你对 BST 定义、递归展开过程和边界条件是否真的有把握。所以刷题时不要背代码要把“为什么这个条件是充分的”想清楚。至于证明可以用归纳法对于上下界解法递归调用前所有祖先已经给当前节点限定了区间节点值只要在区间内并且递归地满足左、右子树的区间约束整棵子树就合法。这样讲逻辑链就完整了。6.2 工程里哪里会用到“验证BST”离开力扣BST 验证也不是纸上谈兵。数据库里的 B-Tree/BTree 虽然不是严格的二叉树但在节点分裂和合并时会做大量有序性校验内存中的红黑树、AVL 树本质也是 BST 加上平衡条件插入删除后如果有序性被破坏整个查找结构就废了。做配置系统的人也会遇到类似场景配置项本身是一个树形结构不同路径下的 key 应该满足某种大小关系校验函数和isValidBST的思路几乎一样。规则引擎、权限树、甚至文件系统的目录排序都能找到 BST 校验的影子。所以这题的解题思路不是孤立的小技巧而是“递归定义 边界传播 遍历顺序”三个基础思维的组合体。这也是为什么大厂面试喜欢考它的原因。6.3 和它直接相关的变体题力扣 98 是很多树形题的“地基”。做明白它之后再看下面这些题会轻松很多力扣 99恢复二叉搜索树。核心就是用中序遍历找到两个位置错误的节点再用交换修复。力扣 230二叉搜索树中第 K 小的元素。中序遍历到第 K 个就是答案。力扣 530 / 783二叉搜索树的最小绝对差。中序遍历后比较相邻差值即可。力扣 98 的扩展场景验证一棵树是否平衡、是否完全二叉树虽然判断标准不同但“遍历 状态维护”的框架是类似的。刷完 98 再去做 99你会发现前者的prev记录技巧在后者错误节点检测里直接复用。这种“一题带一题”的学习方式比单纯堆题量效率高很多。7. 我的个人刷题习惯以及这次留下的几个提醒7.1 先把递归函数往上“屏”住再写主逻辑我刷这题时有个小经验不要先写isValidBST主函数而是先把递归函数dfs/validate的“职责”用一句话说清楚。比如“这个函数判断以 node 为根的子树是否合法并且所有节点值都在 (low, high) 内”。一旦职责明确了边界条件和递归调用就是顺手的事。如果是中序遍历法心里的口头禅是“上一节点不能大于等于当前节点”。把这句口诀放进去代码基本不会写错。7.2 提交失败时先打印中序序列如果你写的版本是收集数组再判断调试时可以先把中序序列打出来看一眼。看到[1, 3, 2]这种序列你能立刻想到只需要检查相邻逆序。看到[1, 1, 2]能意识到重复值被放行了。序列化输出比盯着树形图画半天更直观。我见过不少人提交失败后第一反应是改代码而不是看失败的输入用例。实际上力扣会给出具体树把它转成层序数组对照我上面那张用例表十有八九能定位到原因。7.3 这道题刷完之后最值得记住的三件事第一BST 的两个关键判定工具——中序递增和区间约束——是等价的面试时要能互相转换。第二严格的和加上可以用long或null处理的边界是这道题正确率的分水岭。第三递归、迭代两种形态都要能写因为代码只是思想的载体真正的思考发生在你画出树、推演区间的那十几秒里。最后说点题外话。我给别人讲这道题的时候经常建议他们先别看官方题解而是自己按“这个节点必须比我上一个大”和“这个节点必须在我祖先限定的范围内”两个方向各写一版。能把两个版本都写对并且说出为什么它们等价二叉搜索树的底层理解就真正到位了。很多年后你可能不记得这题代码的每个细节但这个“定义决定解法、解法又反哺定义”的过程会一直留在你的解题直觉里。
