二叉搜索树的判断几乎是算法面试里绕不开的一道门槛题。牛客的BM34题问的就是这个给一棵二叉树的根节点判断它是不是二叉搜索树。别看题目短这背后藏着对二叉搜索树本质的理解、对递归边界的把握还有对编程细节敏锐度。很多人在这道题上栽跟头不是因为不会遍历二叉树而是没有吃透“严格小于”和“严格大于”这两个约束。提前说结论这道题的核心判断依据只有一句话——对二叉搜索树进行中序遍历得到的序列一定是严格递增的。这个结论推导出的解法几乎可以一行行写到面试官的心里去。但真要写出不踩坑的代码还得把递归、全局变量、边界条件都理清楚。不管是准备校招笔试还是社招面试这道题都值得你花半小时彻底吃透。下面我会把思路讲透把三种主流写法都摆出来再把实际运行中最容易遇到的报错场景给你一一拆开。1. 题目还原与核心定义拆解BM34题目的原文描述很简洁但也挖好了坑。它说给定一个二叉树根节点请你判断这棵树是不是二叉搜索树。二叉搜索树满足每个节点的左子树上的所有节点均严格小于当前节点且右子树上的所有节点均严格大于当前节点。注意“所有节点”和“严格”这两个词。很多人在第一次做这道题时会下意识地以为只要比较当前节点和它的左右孩子就够了也就是left.val root.val right.val root.val就万事大吉。这个直觉来自看过的二叉树插图——教科书上画的BST都是局部很规整的树但现实中的二叉树形状奇葩这种局部判断完全不够。先看一个最常见的反例。下面这棵树10 / \ 5 15 / \ 6 20如果只判断每个节点和左右孩子的相对大小这棵树完全满足条件10 大于 5 小于 1515 大于 6 小于 20。但它不是二叉搜索树因为6出现在10的右子树里却比10小。问题就出在6这个节点位于10的右子树它必须大于10可它只有6。再看“严格”二字的含义。二叉搜索树的定义里要求左子树上的所有节点严格小于当前节点右子树上的所有节点严格大于当前节点。注意“严格”意味着相等是不允许的。如果树里有重复值比如根节点是5左子树某个节点也是5那这就不是一棵合法的二叉搜索树。为了帮助你建立直观理解可以把二叉搜索树想象成一本有序的字典中序遍历读出来的顺序必须像字典页码一样从小到大排列。一旦中间出现“倒挂”字典就乱了查找效率也无法保证。这道题适合谁来刷刚入门数据结构的新手可以把它当作理解二叉树遍历的第一个进阶题准备面试的同学则需要把它当作高频题目来对待——它出现的频率在牛客和力扣里都属于第一梯队而且往后学AVL树、红黑树时判断“有序性”的思路还会反复用到。2. 三种解题思路从直觉到最优面对这道题解法不止一种。搞清楚每种解法背后的动机比背代码重要得多。下面按“从直觉到严密”的顺序理一遍主流思路。2.1 经典误区只比较父子节点为什么错先说说最直觉、也最容易错的尝试。很多人的第一版代码长这样public boolean isValidBST(TreeNode root) { if (root null) return true; if (root.left ! null root.left.val root.val) return false; if (root.right ! null root.right.val root.val) return false; return isValidBST(root.left) isValidBST(root.right); }这段代码表面看很合理每个节点都检查左孩子比自己小、右孩子比自己大。但这犯了前面说的错误它只约束了“直接父子关系”没有约束“祖先与后代的关系”。回到那个例子里6 和 10 之间隔了一层15代码根本检查不到它们俩之间的非法关系最后返回true输出错误答案。这类错误在实际刷题时非常隐蔽因为用普通小用例测试都能通过直到遇到稍复杂的树才原形毕露。如果你在牛客或力扣上提交这个版本大概率会在某个测试用例上WA答案错误。2.2 中序遍历法利用BST的天然排序特性为什么说“中序遍历得到递增序列”是判断BST的关键要从二叉搜索树的定义推导。对任意一棵二叉搜索树中序遍历的顺序是先遍历左子树再访问根节点最后遍历右子树。由于左子树所有节点都小于根节点右子树所有节点都大于根节点那么中序遍历把整个树“拉平”之后读出来的序列天然就是从小到大的。反过来如果一棵二叉树中序遍历结果是严格递增的就说明每个节点的左子树都小于它、右子树都大于它——这正好符合BST定义。所以解法就出来了对树做一次中序遍历在遍历过程中检查当前访问到的节点值是否大于前一个访问的节点值。如果中途发现某一步不满足递增关系就可以立刻判定“不是二叉搜索树”。这个思路好在哪里好在对题目本质的把握。它不需要层层传递上下界只需要一个变量记录前驱节点值实现简单也不容易写错。面试中先讲这个思路通常面试官都会点头。2.3 递归区间法显式传递上下界与中序遍历法并列的另一个经典思路是区间约束法。它的核心是每个节点都处在一个取值区间(lower, upper)内如果节点值不在区间内就违规。从根节点开始根节点没有上下界约束所以区间是(-∞, ∞)。进入左子树时把上界收紧为当前节点的值进入右子树时把下界提升为当前节点的值。这样约束一层层往下传递任何一层祖先节点的值都会约束到后代节点。这个思路在代码上用递归实现非常直观每次递归传入lower和upper两个边界值遇到null返回 true检查当前节点值是否落在开区间内然后递归检查左右子树并更新对应的边界。相比中序遍历法区间法更接近“严格定义”的字面意思在讲解时也更容易让面试官理解你的思路。它唯一的注意点是要处理节点值为Integer.MIN_VALUE/Integer.MAX_VALUE时的边界问题这个后面细说。3. 实操代码与易错点解析思路理清了代码怎么写才能既稳又简洁下面给出两种主流程的完整实现并标注容易翻车的细节。3.1 中序遍历法实现Java 版用递归实现中序遍历比较简单需要一个成员变量记录前驱节点public class Solution { private long pre Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if (root null) return true; // 先检查左子树 if (!isValidBST(root.left)) return false; // 再检查当前节点和前驱是否满足递增 if (root.val pre) return false; pre root.val; // 最后检查右子树 return isValidBST(root.right); } }这里有几个细节要特别注意。第一为什么把pre初始化成Long.MIN_VALUE而不是Integer.MIN_VALUE因为题目里的节点值范围是int如果根节点的值恰好是Integer.MIN_VALUE那么root.val pre就会误判成 false。用long的极小值可以避免这个尴尬。第二比较用的是而不是。因为题目要求“严格小于”等于也算违规。这个细节在BM34里至关重要稍微马虎一点就会让带重复值的测试用例漏掉。第三递归过程中提前返回false很重要。只要左子树或者当前节点发现不合法就不需要再递归右子树了这样可以节省时间。不过递归框架决定了即使提前返回也要配合好判断顺序不能让右子树在非法状态被跳过时产生误判。上面这段代码是标准的教科书写法。如果你想更显式地控制中序遍历顺序也可以拆开写public class Solution { private TreeNode pre null; public boolean isValidBST(TreeNode root) { if (root null) return true; boolean left isValidBST(root.left); if (pre ! null pre.val root.val) return false; pre root; boolean right isValidBST(root.right); return left right; } }第二种写法用TreeNode pre存“前一个被访问的节点”在第一次访问时pre为 null所以不会误判断。两种写法等价选择你喜欢的一种即可。3.2 区间法实现Java 版区间法代码更贴近定义而且不需要额外成员变量参数直接传递边界public class Solution { public boolean isValidBST(TreeNode root) { return check(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean check(TreeNode node, long lower, long upper) { if (node null) return true; if (node.val lower || node.val upper) return false; return check(node.left, lower, node.val) check(node.right, node.val, upper); } }这段代码的核心就是那两条递归调用左子树继承当前下界上界变成当前节点值右子树继承当前上界下界变成当前节点值。这样一层层收紧区间非常形象。这里同样用long类型接收边界避免int的 ±∞ 不够用。node.val lower用是为了保证严格大于下界node.val upper用是为了保证严格小于上界。3.3 两种写法怎么选从做题角度中序遍历法更通用。因为“中序遍历有序”这个结论在任何需要验证BST性质的场景里都成立而且以后做“BST的第k小元素”“BST转双向链表”等题时也会用到中序遍历框架熟悉它一举多得。区间法在面试讲解时更好沟通逻辑几乎是翻译题面。但从编码量看两者差不多。我的建议是面试时首选区间法讲思路、中序遍历法写代码这样既有理论深度也展示了扎实的编码能力。其实还有第三种思路——迭代版中序遍历用显式栈来代替递归。这在遇到树深度极大、递归栈溢出时是保命方案后面排查问题时会专门讲到。4. 踩坑实录为什么你写的二叉树程序总是报运行时错误刷过二叉树题目的人应该都体会过那种“明明逻辑没错一运行就报错”的崩溃感。围绕BM34这道题最常见的运行时错误和答案错误无非下面几种逐个看一遍你以后再遇到就能秒定位。4.1 空指针异常对 null 节点直接访问属性这是二叉树题里最高频的运行时错误。写递归时没有判断当前节点是否为 null直接访问node.val、node.left就必然导致NullPointerException。BM34里典型的错误写法是if (root.left.val root.val) return false; // root.left 可能为 null正确的处理方式一定是在使用某个节点之前先判断父节点是否为 null。我个人的习惯是在递归函数开头统一判空if (node null) return true;这样整个函数体内就不会出现针对 null 的访问逻辑也干净。4.2 栈溢出递归层数太深二叉树如果退化成一个单链表形态比如每个节点只有右孩子深度可能达到几万甚至几十万层。递归中序遍历在每一层都会占用栈帧树太深时直接抛StackOverflowError。这种错误在判题系统里通常表现成“运行时错误RE”不会告诉你是栈溢出只能靠经验判断。遇到这种问题最简单的规避方案是把递归改成迭代用显式栈模拟中序遍历public boolean isValidBST(TreeNode root) { DequeTreeNode stack new ArrayDeque(); TreeNode cur root; long pre Long.MIN_VALUE; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); if (cur.val pre) return false; pre cur.val; cur cur.right; } return true; }这段代码用栈把中序遍历顺序完全模拟出来不依赖系统调用栈树再深也不怕。如果你不确定测试数据的深度迭代版是最保险的。4.3 边界值误判int 最小值引发错误当节点值允许取Integer.MIN_VALUE时很多人初始化的pre Integer.MIN_VALUE会导致第一个节点就被判为非法。这个问题很隐蔽因为大部分测试用例不会刚好命中最小值。用long类型做边界是解决这类问题的通用手段把初始值设为Long.MIN_VALUE或Long.MAX_VALUE。如果有更极端的题目要求比如节点值是long类型就需要用null标记“尚未访问过任何节点”的方式来处理。4.4 测试用例设计如何自测不翻车写完代码后建议用下面几类用例自测空树null应当返回 true。单节点[5]应当返回 true。整棵合法BST[5,3,7,2,4,6,8]应当返回 true。非法BST经典的倒挂用例[10,5,15,null,null,6,20]应当返回 false这个用例专治“只比较父子节点”的错误思路。重复值用例[2,2,3]或[5,5]应当返回 false因为值相等不满足严格递增。包含int边界值的用例根节点为Integer.MIN_VALUE右子树还有值验证边界处理是否正确。每次把这几类用例跑一遍基本能覆盖BM34题所有隐藏陷阱。5. 从BM34延伸这个判断思路能用在哪些地方会判断BST只是第一步这个技能在实际工程和后续算法学习里还能用到不少地方。聊几个我实际工作中遇到过的场景你会发现“中序遍历有序”这个性质其实相当值钱。第一验证二叉搜索树是很多平衡树操作的前置步骤。AVL树、红黑树在插入删除后都要验证是否仍满足搜索树性质这种验证代码本质上就是在做BM34的判断。面试时提到这一层会显得你有全局视野而不只是会背题。第二利用中序遍历有序性做“BST转累加树”“BST第k小元素”等问题。这些问题可以直接在中序遍历过程中加一步操作完成框架和BM34一模一样区别只是把比较前驱值换成累加或计数。第三序列化与反序列化的校验。比如从文件里读回一棵树先判断是不是BST再决定用不用二分查找逻辑这种场景虽然不常见但一旦遇到你心里有数。第四理解区间约束对后续的红黑树插入修复、B树分裂都有帮助。区间法里上下界的传递逻辑本质上是把全局约束拆成局部约束逐层传递这个思想在很多带边界条件的算法题里都会复用。最后聊点个人体会这道BM34我前前后后给不少人讲过。多数人第一次写出来的版本都是某个“仅比较父子节点”的变体这几乎是逃不掉的弯路。我自己第一次做这道题时也提交过WA错在把root.left.val root.val写成了导致重复值用例没拦住。后来我把这三种思路都在本子上推了一遍——错误直觉、中序遍历、区间约束——才发现这道题真正的价值不是让你记住某个模板而是逼你想清楚“判断BST”到底在判断什么。你越深入理解这个“为什么”后面写AVL、写红黑树、写各种需要维护有序性的数据结构时就越不容易踩坑。如果你刚开始刷二叉树建议把BM34当作一个里程碑写对递归结构、处理好边界条件、再试着把它改成迭代版。这三件事都做到了二叉树这类题你基本就有了稳定的手感。最后再分享一个小经验如果你在牛客上提交BM34时反复报错先别急着怀疑题目数据有问题。检查一下自己是不是在递归里用了int类型的pre检查一下空节点判断放的位置检查一下比较符号是不是绝大多数问题都出在这三个地方。