刷题刷到BM34的时候我第一反应是这不是送分题吗判断一棵二叉树是不是二叉搜索树定义都给你写好了——左子树所有节点严格小于当前节点右子树所有节点严格大于当前节点直接递归不就完事了结果真上手写代码才发现这题的水比想象中深。牛客网上的BM34透过每个节点的左子树上的所有节点均严格小于当前节点这句话其实在考你有没有理解二叉搜索树的全局性质。很多人包括最开始的我栽在同一个坑里只检查当前节点和它的直接左右孩子而忽略了整棵子树的约束。这篇文章我想把BM34这道题讲透。先拆题目再讲三种主流解法——中序遍历判定、递归上下界判定、以及面试加分项的Morris遍历——然后把我实际调试过程中踩过的坑、遇过的报错、总结的测试用例全部整理出来最后再聊几个从BST衍生出来的经典变体。准备面试的同学或者刷完题想深入理解的兄弟这篇应该能给你省下不少时间。1. 题目理解与思路拆解1.1 定义拆解为什么所有两个字才是关键先回到原题给定一棵二叉树的根节点判断这棵树是不是二叉搜索树。二叉搜索树满足每个节点的左子树上的所有节点均严格小于当前节点且右子树上的所有节点均严格大于当前节点。你可以把每个节点想象成一个关卡管理员它负责整片辖区的数值范围。往左走你去的是一片每个值都必须比关卡低的区域往右走则是每个值都必须比关卡高的区域。重点在这个所有上——不是左孩子小于当前节点就完事而是左子树里最深处的叶子也得小于当前节点。这个全局约束是BST的命根子也是面试官最想看到的理解深度。因为BST养着一条隐形的大小链条如果对它做中序遍历——先左、再根、后右——得到的序列一定是严格递增的。换句话说一棵树是BST等价于它的中序遍历结果严格升序。这个等价关系是后面很多解法的理论基础。还有一个隐藏考点题目说的是严格小于、严格大于。这意味着BST里不允许出现重复值。如果某棵树里有相等节点在严格的定义下它直接出局。这个细节如果没注意代码里写成还是就会天差地别。1.2 最容易错的直觉陷阱很多人第一步想出来的解法是递归检查三个东西左孩子小于根、右孩子大于根、左右子树分别又是BST。听起来没问题但它漏掉了跨层级的约束。看下面这个经典反例10 / \ 5 15 / \ 6 20节点5小于1015大于106小于1520大于15每个节点单独看都很守规矩。但整棵树根本不是BST因为6在10的右子树里却比10小。这就是局部有序和全局有序的区别。打个比方你按学号让学生从矮到高排成一列光检查相邻两个人没站错还不够整个队伍必须从前到后严格递增才行哪怕中间隔了十个人前面的人也绝不能比后面的人高。二叉搜索树要的就是这种全链条的有序而不是邻居之间的局部有序。所以判断BST只做局部检查是不够的必须把信息传递下去。怎么传递方法无非三种用中序遍历的自然升序性质、用递归时的上下界参数、用Morris遍历在 O(1) 空间里完成中序检查。下面逐个说。2. 三种主流解法一次讲透2.1 中序遍历判定法最符合直觉的思路中序遍历是二叉树所有遍历方式里和BST关系最近的一个。原因很简单BST的中序序列严格递增反过来只要一棵二叉树的中序序列严格递增这棵树就是BST。这个解法的实现分两步先把树中序遍历完在遍历的过程中维护一个前驱节点prev。每次访问到新节点时拿当前节点和prev比一比如果当前节点值小于等于prev的值直接判定不是BST。这里为什么是小于等于而不是小于因为题目要求严格小于/严格大于如果允许相等那[1, 1, 1]这种树也会被判成BST显然不对。改一个符号结果完全相反这种细微处恰恰是面试时口述思路最容易暴露问题的地方。我最初写这道题时中序遍历用的是递归。递归写法的执行顺序天然满足左-根-右代码很简短但有个坑prev这个变量在递归过程中必须能跨层共享。Java里面基本类型按值传递直接传long prev进去改完的值上一层看不到。解决办法有几个最省事的是用一个long[] prev new long[1]装到数组里或者在类里加一个成员变量。如果不想用递归也可以用显式栈做迭代中序遍历。思路是先把根节点的所有左孩子入栈然后逐个弹出访问访问完一个节点后如果有右孩子就把右孩子及其所有左孩子入栈继续弹。迭代的代码看起来比递归长一点但它有个好处不会因为树的深度太大而爆栈。这两种写法我在日常刷题里都用过实测下来面试时如果没特别要求我更推荐迭代写法因为它对栈空间的讨论更可控。2.2 递归上下界法把全局约束编码进参数如果说中序遍历是从结果反推性质那递归上下界法就是从过程直接执行规则。思路是每次递归进入一棵子树时带上两个边界值lower和upper表示这个子树里所有节点必须落在(lower, upper)开区间内。初始时根节点的范围是整个整数域用Long.MIN_VALUE到Long.MAX_VALUE表示。往左子树走时右边界收紧到当前节点值往右子树走时左边界收紧到当前节点值。为什么这样设计因为BST的约束本质上是沿着树枝层层传递的。一个节点一旦成为某节点的左后代它就必须小于路径上每一个祖先节点。我们要做的就是把祖先们的要求打包成边界传下去。每走一层边界就收紧一点范围越来越窄直到叶子节点。这个解法的正确性非常好解释代码也短面试时想快速展示思路推荐先说这个。但细节里有三个容易翻车的地方第一边界一定要用long不能用int。如果节点值正好是Integer.MIN_VALUE或Integer.MAX_VALUE用int做边界会把本来合法的节点误判成非法。第二比较时要用开区间即node.val lower或node.val upper时返回 false这样天然处理了重复值问题。第三递归处理空节点时直接返回 true空树和空子树都是合法的。我在给朋友讲这个思路时爱用一个类比想象你在山路上开车路的两边有护栏左边护栏是lower右边护栏是upper。每经过一个节点护栏就往里收一截。只要车冲出护栏这条路就不合格。这个比喻能帮你记住边界是动态收紧的。2.3 Morris遍历空间 O(1) 的进阶解法Morris遍历是我到了很久之后才真正理解的解法它解决的是中序遍历必须用栈或递归、空间复杂度至少 O(h)这个痛点。它的核心思想是借用树上闲置的空指针当线索实现空间 O(1) 的中序遍历遍历结束后再把树还原。具体到判BST就是在中序访问节点时做和上一种解法完全一样的递增判断。具体步骤分两种情况当前节点没有左孩子直接访问当前节点然后走向右孩子。当前节点有左孩子先找到左子树中最右的节点也就是中序遍历里当前节点的前驱节点pred。如果pred.right为空说明左子树还没遍历完把pred.right临时指向当前节点建立一条回头路然后走向左孩子如果pred.right已经指向当前节点说明左子树遍历完了这时把pred.right恢复为空访问当前节点走向右孩子。原理上这相当于把树从二叉树临时改造成线索树让每个节点在被访问前都能通过前驱的右指针找回来所以不需要额外栈空间。实操中有两点提醒第一Morris遍历会短暂修改树的结构虽然最后会还原但如果在只读场景或者并发环境下直接用它是不合适的面试时要主动说明这一点。第二写Morris的循环时最容易忘的是第二次访问到节点时要恢复pred.right null忘掉这行代码会导致树被改坏后面的判断全部失真。从面试角度说Morris属于加分项。如果前面两种解法你都讲清楚了再补一句我还能用Morris把空间压到 O(1)面试官一般会另眼相看。但如果你对它的指针操作还不够熟建议实际刷题时先跑通代码再考虑面试展示的问题。3. 代码实现与细节打磨3.1 中序遍历的迭代与递归完整实现先给递归版本适合作为讲解时的第一份参考。我用Java写prev用一个长度为1的数组包装规避按值传递的问题public boolean isValidBST(TreeNode root) { return inOrder(root, new long[]{Long.MIN_VALUE}); } private boolean inOrder(TreeNode node, long[] prev) { if (node null) { return true; } if (!inOrder(node.left, prev)) { return false; } if (node.val prev[0]) { return false; } prev[0] node.val; return inOrder(node.right, prev); }这里我直接把prev初始化为Long.MIN_VALUE省去了判空的麻烦。因为题目保证节点值都是32位整数任何合法节点值都比Long.MIN_VALUE大所以第一轮比较不会误伤。再看迭代版本。这是我最常用的写法因为栈空间可控逻辑也顺public boolean isValidBST(TreeNode root) { DequeTreeNode stack new ArrayDeque(); TreeNode cur root; long prev Long.MIN_VALUE; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); if (cur.val prev) { return false; } prev cur.val; cur cur.right; } return true; }注意循环的终止条件cur ! null || !stack.isEmpty()两者缺一不可。如果只写!stack.isEmpty()当根节点的左子树为空、栈也弹空时会漏掉后续的右子树节点如果只写cur ! null则访问完某个节点的右子树后栈还没清空就退出了。这个条件我亲眼见过好几个同学写错过排查半天才发现是循环边界。如果你用Python刷题迭代版可以写得非常紧凑def isValidBST(root): stack [] cur root prev float(-inf) while stack or cur: while cur: stack.append(cur) cur cur.left cur stack.pop() if cur.val prev: return False prev cur.val cur cur.right return True3.2 上下界递归的边界处理递归上下界法的实现我前面给过框架这里补充几个实际工程里必须注意的细节。第一用long还是int这是最容易忽略又最容易出事的点。假设初始上界用Integer.MAX_VALUE而根节点恰好也是Integer.MAX_VALUE那么node.val upper会判定为 true一棵合法的单节点BST直接被误杀。换成Long.MAX_VALUE就完全没这个问题反正树节点的值最多32位32位数和64位数之间留出了一个充足的缓冲区。第二递归方向别写反。往左子树递归时新的上界是当前节点值下界保持不变往右子树递归时新的下界是当前节点值上界保持不变。写成check(node.left, node.val, upper)和check(node.right, lower, node.val)才对。这个规则可以用缩小合法区间来记忆每层递归都在把上一层的区间切成两半一半分给左子树一半分给右子树。第三注意空节点判断和短路逻辑。代码一般是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); }这里左边的左子树检查一旦失败右边就不会执行了效率上没问题。但如果你在两个递归调用前后还写了别的逻辑务必要想清楚执行顺序别把判断放到递归之后导致白跑一趟。3.3 测试用例设计清单提交代码之前我习惯把下面这份测试用例按顺序过一遍。这张表是从真实翻车经历里总结出来的每一条都能对应一个常见的错误写法。用例树结构期望结果能拦截的错误空树nulltrue忘判空导致空指针单节点[5]true边界初始化和负数干扰合法BST[2,1,3]true基本逻辑正确性经典反例[5,1,4,null,null,3,6]false只检查直接左右孩子跨层反例[10,5,15,null,null,6,20]false只检查直接左右孩子重复值[1,1,1]false把写成极值节点[Integer.MIN_VALUE]true用int做上下界链状退化树[1,null,2,null,3]true递归深度/自平衡混淆其中跨层反例[10,5,15,null,null,6,20]我建议你亲手跑一遍自己的代码盯着调试器看它到底在哪一步返回错误。只有亲眼看到6这个节点是怎么混进右子树的你才会真正理解全局约束的含义。4. 常见报错与排查思路实录4.1 运行时错误有哪些典型症状刷题平台上这类题目的报错最典型的有三种空指针异常、栈溢出、数组越界。空指针异常几乎都出在递归的入口和左孩子右孩子的访问上。比如递归函数开头忘了写if (root null) return true那么当遍历到叶子节点的空孩子时一访问.val直接炸。还有一种隐蔽情况我习惯用DequeTreeNode时pop()之前没有判空而循环条件又写错了导致栈已经空了还在弹。栈溢出通常不是代码逻辑写错而是树的形态太极端。比如[1,null,2,null,3,null,4]这种斜着一路往右的链状树如果用了递归中序遍历调用深度就是节点数量级节点一多必爆。刷题平台一般递归深度限制在千级但极端测试数据可能轻松造出一万层。这题如果想稳迭代栈或者Morris更保险。数组越界则出现在另一种实现风格先把中序遍历结果收集到一个数组或列表里再单独循环判断是否递增。这种写法思路最简单但容易在只收集了一半就判断或者数组下标从1开始但初始化成从0开始这类低级错误上翻车。我建议直接用流式的对比也就是维护一个prev边遍历边比省掉一个数组的空间也省掉一类错误。4.2 逻辑错误的三种隐蔽场景第一种只比较当前节点和直接左右孩子。这个前面已经反复强调是最经典的逻辑漏洞面试官专门用它来试你有没有真的理解BST。第二种重复值处理。严格递增的条件下树里出现两个相同的值就应该返回 false。很多人写判断条件时顺手写了结果把[1, 1, 1]这种树判成了BST。这个问题在口头解释时最容易暴露因为有经验的面试官会追问节点值相等你怎么处理。我的习惯是默认按题面严格处理写成如果题目允许相等再和面试官确认后改成。第三种把初始上下界设成了Integer.MIN_VALUE到Integer.MAX_VALUE。如果节点值恰好等于这个边界值开区间判断会直接误伤。这也是我在3.2里反复强调用long的原因。遇到这种边界建议直接构造一条测试数据当场验证比空想快得多。4.3 调试技巧怎么快速定位错误节点如果你用本地IDE调试我推荐一个笨但有效的方法在递归的每个访问节点的地方打印当前节点值、prev值和期望区间。比如这样访问节点: 6, prev: 5, 期望区间(10, 15)一眼就能看出6不在区间内因为6 10。如果用的是中序遍历方案就直接打印中序序列比如得到[5, 6, 15, 10, 20]找第一处逆序对15 10那个10就是破坏BST性质的节点。还有个实用小技巧如果测试数据很大肉眼看不完可以写一个辅助函数把树的中序序列转成字符串和期望的严格递增序列做差集定位第一个不相等的索引。这个方法在刷题时帮我不止一次快速定位到问题节点比在代码里设断点一步步跟快很多。5. 延伸从BST到经典变体训练5.1 恢复二叉搜索树BM34还有一个经典变体二叉搜索树中的两个节点被错误地交换了值要求在 O(1) 空间的约束下恢复它。这道题本质还是中序遍历抓逆序。交换两个节点后中序序列里会出现一处或两处逆序对。如果是相邻节点被交换只有一处逆序如果不相邻会有两处。找到逆序对之后把对应节点的值交换回来即可。我在写这道题时踩过的一个坑是逆序对可能不止一对。第一次遇到逆序时先记录两个节点第二次遇到逆序时要更新第二个节点而不是直接返回。这个细节如果不留意遇到10和5交换这种不相邻的情况就会恢复失败。做这道变体之前强烈建议先把BM34的中序遍历解法写到闭着眼都能默的程度。5.2 从排序数组构建高度平衡BST另一个高频变体是给你一个升序排序的数组构建一棵高度平衡的BST。解法很直观每次取数组中间元素作为根左边递归构建左子树右边递归构建右子树。选择中间元素的原因是保证左右子树高度差不超过1。这个题考的是对递归分治的理解也顺便复习了BST和中序序列的关系一棵BST的中序序列就是排序数组反过来用排序数组重建BST本质上是在做中序序列还原树。熟悉BM34的判定逻辑后你会更加理解中序和BST之间的双向绑定关系。5.3 变体题的通用方法论刷了几个变体之后你会发现一个通用的套路凡是和BST性质相关的问题第一反应都应该是中序遍历。有序性、逆序对、相邻节点关系这些问题放到中序序列里都变得非常直观。第二反应才是区间传递也就是递归上下界适用于需要逐节点验证约束的问题。这两个方法论一个面向检查一个面向构建配合使用能覆盖大部分BST题目。另外要注意的是实际问题中BST很少以裸树形式出现更多是自平衡的AVL或红黑树但判断这棵树是否符合BST性质的方法论是完全通用的。你甚至可以把BM34的判定逻辑封装成一个工具函数在测试自平衡树时反复调用非常实用。6. 最后再分享几个实操心得刷完BM34我对算法题里最危险的就是看似简单的题这句话有了新的理解。这道题表面上看就是一行递归的事实际上考了全局约束意识、边界处理、空间复杂度权衡甚至能延伸到面试官追问的许多变体。我的建议是不要满足于AC至少把中序遍历和递归上下界这两种解法都默写一遍Morris那种进阶解法可以根据自己的精力安排但一定要能讲清楚它为什么是 O(1) 空间。另外想强调一个习惯每次写完代码先把边界测试用例过一遍。空树、单节点、重复值、极值、链状树这五类用例大概需要两分钟却能在提交前拦截掉绝大多数错误。我在实际面试时也习惯先用口头描述边界情况再写代码这能让面试官感觉你考虑问题很周全。最后分享一个我调整这个题目时做的扩展实验把判定函数改造成返回第一个违反BST性质的节点用来在一棵坏树上快速定位出错点。这个小工具后来在调试恢复二叉搜索树的变体时帮了大忙。建议你也试试把一道题的解法拆开重组往往比刷十道题更能锻炼对数据结构的理解。