LC.99恢复二叉搜索树：中序遍历定位错误节点与Morris O(1)解法

刷题刷到 LC.99 的那天晚上我盯着恢复二叉搜索树这六个字想了很久一棵二叉搜索树里只有两个节点的值被错误交换要我把它恢复成合法状态。第一反应是这怕不是要重建整棵树结果冷静下来才发现这道题表面上是二叉树操作骨子里考的是中序遍历的性质。一篇文章把这道题的完整解法和踩坑过程写清楚从暴力思路到 O(1) 空间的 Morris 遍历都覆盖适合正在刷二叉树、准备面试算法轮的朋友。1. 拿到题目先别急着建树LC.99 到底在考什么1.1 题目描述与表面难点题目本身不长一棵二叉搜索树Binary Search Tree简称 BST中恰好有两个节点的值被错误地交换了。要求你在不改变树结构的前提下恢复这棵 BST。进阶要求是使用 O(1) 空间复杂度完成。这里有个关键词容易被忽略不改变树结构。很多第一次看到这题的人脑子里第一个蹦出来的方案是中序遍历一遍把值存进数组排序后重新填回去。这个方案确实能让树恢复合法但它本质上是在做值重建而不是修复两个被交换的节点的值。树的结构确实没变可每个节点上的值都被重新洗牌了一遍这不满足题目隐含的最小修改语义更别谈空间复杂度了——存一个长度为 n 的数组就是 O(n) 的空间。我第一次做的时候也走在这条道上写到一半觉得不对劲题目只交换了两个节点的值我凭什么把整棵树的值都重新排一遍这就好像一本书里有两页装订反了正常做法是把这两页换回来而不是把整本书的页码全部重新编排。1.2 为什么重建一棵树是最差解顺着这个思路往下想重建值这个方案还有一个更致命的缺陷它依赖于排序后回填这个操作而排序的结果会破坏原始树中节点与值之间的对应关系。举个简单的例子一棵 BST 中序遍历结果是[1, 6, 3, 4, 5, 2, 7]这里面2和6被错误交换了。如果我用排序回填方案排序后变成[1, 2, 3, 4, 5, 6, 7]然后按中序遍历的顺序依次把值写回每个节点。做完之后树确实是一棵合法的 BST 了但原本那个值为6的节点现在变成了2原本值为2的节点变成了6中间所有节点都被动改了值。这不是题目要的恢复是再造。说到底LC.99 考察的是你能不能精准地找到那两个错位的节点然后只交换它们的值。这需要你理解 BST 的根本性质而不是盲目套用中序排序这种万金油。1.3 题目的名字已经把答案写在门上了LC.99 的标题后面跟着(中序遍历)这不是随随便便加的一个备注它就是整道题的解题钥匙。二叉搜索树有一个极其重要的性质中序遍历的结果是严格递增的序列。如果这棵树里有两个节点的值被交换了那么中序遍历的结果一定会在某些位置上破坏递增性。找到这些破坏点就找到了那两个错误的节点。所以这道题的解题思路可以概括成三句话第一中序遍历整棵树第二在遍历过程中找出破坏递增序的两个节点第三把这两个节点的值交换回来。接下来所有内容都是围绕这三句话展开的。2. 中序遍历的有序性从树到数组的降维2.1 二叉搜索树的核心性质二叉搜索树的定义我就不啰嗦了简单说就是对于任意一个节点它左子树上的所有节点的值都小于它右子树上的所有节点的值都大于它。这个定义直接推导出一个结论对 BST 做中序遍历左子树、根节点、右子树得到的序列必然是严格递增的。这个性质的价值在于它把一棵看似复杂的树结构压缩成了一维的递增序列。树上的问题很多时候可以转化成序列上的问题。LC.99 就是典型代表——你要在树上找两个错位的节点等价于在一个递增序列中找两个错位的元素。给个小测试用例感受一下。假设正确 BST 是这样的4 / \ 2 6 / \ / \ 1 3 5 7它的中序遍历结果是[1, 2, 3, 4, 5, 6, 7]完美递增。如果我把节点2和节点6的值交换树变成4 / \ 6 2 / \ / \ 1 3 5 7中序遍历结果变成[1, 6, 3, 4, 5, 2, 7]。注意看这个序列里有明显的降序段6 3以及5 2。这就是突破口。2.2 两个节点被交换后中序序列长什么样现在我们要回答一个关键问题两个节点在 BST 中被错误交换中序序列里到底会呈现什么规律先说结论中序序列里会出现一处或者两处降序位置取决于被交换的两个节点在原序列中是否相邻。如果被交换的两个节点在中序序列中是相邻的那么交换后只会出现一处降序。比如[1, 2, 3, 4, 5]中交换3和4得到[1, 2, 4, 3, 5]只有4 3这一处降序。如果被交换的两个节点在中序序列中是不相邻的那么交换后会出现两处降序。还是用刚才的例子[1, 2, 3, 4, 5, 6, 7]交换2和6得到[1, 6, 3, 4, 5, 2, 7]降序出现在6 3和5 2两个位置。为什么会出现这种差异因为把一个大数6提前挪到了位置2占的位置它比后面的3、4、5都大所以第一个降序位置出现同时把小数2放到了位置6原来的地方它比前面的5小所以第二个降序位置出现。相邻交换时由于两个数紧挨着只有一个大数放在了小数前面的地方所以只有一处降序。2.3 降序位置的数学特征一次还是两次搞清一次降序和两次降序的区别之后识别错误节点的规则就非常清晰了两处降序的情况第一个降序位置的前一个元素较大的那个是第一个错误节点第二个降序位置的后一个元素较小的那个是第二个错误节点。一处降序的情况这一处降序的两个相邻元素正是被交换的两个错误节点。用代码的表达去描述这个过程会发现一个非常优雅的写法。我们维护两个指针first和second再维护一个prev记录中序遍历中当前节点的前驱。在遍历过程中只要发现prev.val current.val就说明遇到了降序位置。此时if (first null) { first prev; // 第一个降序位置的前一个节点一定是第一个错误节点 } second current; // 每次遇到降序都更新第二个错误节点这段逻辑的精妙之处在于当只有一处降序时second最终就指向这一处降序的后一个节点正好是相邻交换中的第二个错误节点当有两处降序时first在第一处降序被赋值为较大的那个节点second经过第二处降序的覆盖最终指向第二个降序的后一个节点也就是较小的那个错误节点。一个简单的持续覆盖操作同时兼容了相邻和非相邻两种情形。3. 识别两个错误节点的核心逻辑一次降序和两次降序的不同处理3.1 常规判定逻辑的推导我见过有的解法去判断降序出现几次然后分情况讨论代码倒是写不坏但分支一多就容易出问题尤其是相邻交换时很容易漏掉第二个节点。最干净的思路就是前面说的first只赋一次值second每次都覆盖。我们来推导一下为什么这样就是对的。假设中序序列为a1, a2, ..., an它本该严格递增但现在有两处异常。情形一序列中有一处降序即存在唯一的位置k使得ak a(k1)。这说明交换就发生在ak和a(k1)这两个相邻元素之间。我们的代码在遍历到a(k1)时会检测到降序此时prev就是akcurrent就是a(k1)。first aksecond a(k1)正好就是这两个错误节点后续不会再触发别的降序。情形二序列中有两处降序即在位置p和位置q处p q分别有ap a(p1)和aq a(q1)。这种情况的本质是被交换的两个元素相距较远较大的那个被放到了ap位置较小的那个被放到了a(q1)位置。代码在位置p处第一次触发降序first ap在位置q处第二次触发降序second被覆盖成a(q1)。最终first apsecond a(q1)恰好是那两个被交换的节点。所以你看这个写法的妙处在于它不需要记录这是第几次降序只需要把first锁死在第一次降序的prev上把second持续更新为每次降序的current。无论哪种情形结果都对。情形降序数量正确识别结果代码行为相邻交换1该降序相邻的两个节点first 记录较大节点second 记录较小节点非相邻交换2第一处降序的前驱 第二处降序的后继first 锁第一处second 被第二处覆盖3.2 代码里如何用两个指针完成识别把逻辑落到代码上核心就这几行TreeNode prev null; TreeNode first null; TreeNode second null; void inorder(TreeNode node) { if (node null) return; inorder(node.left); if (prev ! null prev.val node.val) { if (first null) first prev; second node; } prev node; inorder(node.right); }很多人在第一次实现时会有个疑问为什么prev要在中序遍历中间更新而不是进入递归前更新因为中序遍历的节点访问顺序就是左子树、当前节点、右子树。我们拿当前节点和它在中序序列中的直接前驱比较必须等左子树全部遍历完这个直接前驱才会被更新到正确的值。你把prev node放在访问当前节点之后就等于确认了前驱已经是最新值然后继续去右子树里找下一个要比较的节点。3.3 常见错误只处理了相邻交换漏掉非相邻交换这里我要专门提一个坑。我第一次写的时候是这么判断的if (prev ! null prev.val node.val) { if (first null) { first prev; second node; } else { second node; } }看起来差不多其实有个隐患。如果两处降序中间还隔着正常的递增段这个写法没问题但如果第二处降序和第一处降序紧挨着或者是相邻交换的那一处降序逻辑就会乱。更常见的错误是有人写成这样if (first null prev.val node.val) { first prev; second node; } else if (prev.val node.val) { second node; }本质一样问题不大。真正容易翻车的是把second只赋值一次if (prev.val node.val) { if (first null) { first prev; second node; // 这里把 second 固定了 } // 第二处降序根本没有更新 second }如果是两个不相邻的节点被交换前面例子[1, 6, 3, 4, 5, 2, 7]中第二处降序5 2的位置根本没进去判断second永远停留在3上。最后你会把6和3交换结果树还是错的。所以记住了second必须要持续更新不能只赋值一次。4. 递归版完整实现从遍历到修复只差三步4.1 可提交的完整代码附注释把识别逻辑和修复逻辑拼在一起递归版就完整了。我用 Java 和 Python 各写了一个版本直接可以提交。Java 版本class Solution { private TreeNode first null; private TreeNode second null; private TreeNode prev null; public void recoverTree(TreeNode root) { // 第一步中序遍历找出两个错误节点 inorder(root); // 第二步交换两个节点的值 if (first ! null second ! null) { int tmp first.val; first.val second.val; second.val tmp; } } private void inorder(TreeNode node) { if (node null) return; // 中序左 - 根 - 右 inorder(node.left); // 访问当前节点比较是否存在降序 if (prev ! null prev.val node.val) { if (first null) { first prev; } second node; } prev node; inorder(node.right); } }Python 版本class Solution: def recoverTree(self, root: TreeNode) - None: self.first None self.second None self.prev None def inorder(node): if not node: return inorder(node.left) if self.prev and self.prev.val node.val: if not self.first: self.first self.prev self.second node self.prev node inorder(node.right) inorder(root) if self.first and self.second: self.first.val, self.second.val self.second.val, self.first.val核心代码量不到二十行。整个流程就是中序遍历找节点、交换值。没有别的花活。4.2 为什么要交换 val 而不是交换节点引用这个点值得展开讲讲。有时候你搜题解会看到有人写成交换两个节点对象就是让first和second的引用互换。这种做法非常危险。树的节点之间是通过左右指针连接的交换引用意味着你要改first的父节点指向secondsecond的父节点指向first还得处理它们之间的左右子树归属。两个节点可能相距很远改起来要处理一堆边界条件而且极容易把树结构弄乱。更重要的是BST 的合法性只依赖于节点值之间的大小关系和节点本身是谁没有关系。我只要把两个节点的值交换回来树的所有父子关系、兄弟关系都不用动整棵树自动恢复合法。这个思路也可以用一句话概括只交换内容不交换位置。这也是为什么题目描述里特意强调不改变树结构——它其实是在暗示你走交换值这条路。4.3 边界条件空树、单节点、根节点参与交换不管树是空还是只有一个节点处理逻辑都非常安全。空树的话inorder(root)进去就直接返回first和second都是null后面的交换判断if (first ! null second ! null)自动跳过。单节点同理没有prev和当前节点的比较两个指针保持null什么都不做。根节点参与交换的情况也自然被覆盖。比如根节点4和某个节点6的值被交换了根节点在遍历过程中被当作普通节点和它的中序前驱比较照样会被识别为一个错误节点。它是不是根不影响算法逻辑因为中序遍历本身不区分节点的层级。5. 空间优化Morris 中序遍历把空间压到 O(1)5.1 线索二叉树的直觉把空右指针利用起来递归版虽然简单但问题是递归栈的深度是 O(h)h是树高。如果树退化成一条链h就等于n空间复杂度就是 O(n)。进阶要求 O(1) 空间怎么办答案是 Morris 遍历。这个名字如果你不熟可以把它理解成一种临时修改树结构、用完再改回来的遍历技巧。它的核心思想是利用节点上大量的空指针特别是空闲的右指针来记录回溯的路径从而省掉栈。具体到中序遍历Morris 的思路是对于当前节点cur如果它有左子树就找到左子树中中序遍历最后一个被访问的节点也就是左子树中最右的节点叫它predecessor。这个predecessor的右指针正常情况下是空的。我把它临时指向cur这样当我遍历完左子树后就能顺着这个指针回到cur不需要栈来记住回来的路。一句话总结用空右指针当线索把递归栈的活干了。5.2 Morris 遍历的 visit 时机详解Morris 遍历最让人头晕的地方是一个节点可能会被访问两次。第一次是通过建立线索的方式到达它第二次才是真正应该处理它的时机。具体来说当我们处理当前节点cur时分三种情况cur.left null没有左子树当前节点就应该立即被处理visit然后cur cur.right。cur.left ! null找到左子树的最右节点predecessor。如果predecessor.right null说明还没建立线索把predecessor.right指向cur然后cur cur.left继续去处理左子树。如果predecessor.right cur说明线索早就建好了左子树已经遍历完此时应该处理当前节点cur然后断开线索predecessor.right null接着cur cur.right。注意看cur.left null和predecessor.right cur这两种情况下cur才是真正被访问的时机。在这些时机里我们用prev和cur做降序判断逻辑和递归版完全一样。5.3 完整实现与时间复杂度证明看完理论直接上代码。我把 LC.99 的 Morris 版本写出来class Solution { public void recoverTree(TreeNode root) { TreeNode first null; TreeNode second null; TreeNode prev null; TreeNode cur root; while (cur ! null) { if (cur.left null) { // 没有左子树直接访问当前节点 if (prev ! null prev.val cur.val) { if (first null) first prev; second cur; } prev cur; cur cur.right; } else { // 找到左子树的最右节点 TreeNode predecessor cur.left; while (predecessor.right ! null predecessor.right ! cur) { predecessor predecessor.right; } if (predecessor.right null) { // 第一次到达 cur建立线索去左子树 predecessor.right cur; cur cur.left; } else { // 左子树遍历完毕恢复树的原始结构 predecessor.right null; // 此时才真正访问 cur if (prev ! null prev.val cur.val) { if (first null) first prev; second cur; } prev cur; cur cur.right; } } } if (first ! null second ! null) { int tmp first.val; first.val second.val; second.val tmp; } } }关于时间复杂度看起来while循环里还有找predecessor的内层循环但 Morris 遍历的每个节点最多被找前驱两次一次是建立线索一次是清理线索。每条边最多走两遍所以总时间复杂度仍然是 O(n)。空间上只用了几个固定指针是真正的 O(1)。如果你面试官问你能不能不用递归做这道题Morris 版本就是最好的答案。不过我得提醒你面试中优先写递归版代码更短更不容易错Morris 更多是展示你懂这个技巧前提是你真的搞懂了线索的建立和清理不然现场写容易翻车。6. 我在本地 Debug 时踩过的坑与验证方法6.1 测试用例构造手搓一个被交换的 BST算法题写完了最怕的是没有好的测试用例。我分享一个自己常用的构造方法先写一个函数按 BST 规则生成一棵合法树然后做一次中序遍历把节点列表存下来随机交换其中两个节点的值。这样无论跑多少组结果都是可预期的。我一般用[1, 2, 3, 4, 5, 6, 7]对应的满二叉树来做测试。假设交换2和6验证一下恢复后的中序序列是不是变回[1, 2, 3, 4, 5, 6, 7]。另外还要专门测试交换两个相邻节点的情况比如交换3和4因为相邻交换只有一处降序最容易在代码里被漏掉。6.2 被误解的第二个节点为什么 second 要一直更新我自己第一次调试 LC.99 时就是被第二个节点这个概念坑了。我一开始把second理解为第二个降序位置的节点写出来的代码是if (prev ! null prev.val node.val) { if (first null) { first prev; } else { second node; } }然后用相邻交换的测试用例一跑交换3和4中序变成[1, 2, 4, 3, 5, 6, 7]。此时只有一个降序位置first被赋值为4但second因为没有第二个降序位置始终是null。最后交换时if (first ! null second ! null)直接跳过整棵树保持原样恢复失败。把second node从else分支里拿出来换成每次降序都更新问题立刻解决。这就是为什么我前面反复强调持续覆盖它不是为了代码简洁而是为了兼容只有一处降序的相邻交换场景。这个坑只要踩过一次以后写相关代码都会很敏感。6.3 使用全局变量还是局部变量的取舍还有一个工程上的细节。递归版里first、second、prev这三个变量如果写在递归函数里作为参数传递你会发现很难同步更新——因为当你往下递归时子调用对prev的修改根本传不回父调用。所以在类里面把它们设为成员变量或者用self.xxx才能在整棵树的遍历过程中共享状态。这是 Java 和 Python 写这道题时最容易犯的错。如果你不想用成员变量也可以把这些状态包装成一个长度为 3 的数组或一个小对象传进递归函数但可读性会差很多。我的建议是直接声明成成员变量把recoverTree方法当作对外入口inorder作为辅助方法逻辑最清晰。7. 复杂度总结与这类题的迁移思路7.1 三种思路的复杂度对比到这里这道题的主流解法都过了一遍。我把它们放在一张表里方便对比方案时间复杂度空间复杂度优点缺点中序存数组 排序回填O(n log n)O(n)思路最简单破坏了原始对应关系空间大递归中序遍历 交换值O(n)O(h)代码短思路直观链状树时空间退化为 O(n)Morris 中序遍历 交换值O(n)O(1)满足进阶空间要求逻辑复杂需理解线索机制实际笔试和面试场景中我推荐优先实现递归版。它已经能覆盖绝大多数要求而且写错的可能性小。如果面试官专门追问能不能 O(1) 空间再亮出 Morris 版本还能展示你对树遍历的理解深度。7.2 从 LC.99 看到的通用解题模型LC.99 给我最大的启发不是 Morris 遍历本身而是BST 问题优先想中序这个思维习惯。大量 BST 相关的题目最终都会落到中序序列的处理上验证一棵树是不是 BST可以用中序遍历检查是否严格递增。找 BST 中第 K 小的元素中序遍历到第 K 个即可还能配合剪枝。求 BST 的中序后继或前驱本质就是在中序遍历中找位置关系。一旦你把这个模型装进脑子里看到新的 BST 题目时第一反应就不是去纠结怎么递归改树而是先想这题的中序序列有什么规律。很多看似复杂的树题在中序序列的视角下都会变得非常直接。LC.99 就是最好的例子树上两个节点的错位映射到序列上只是两处降序一个循环就解决了。7.3 一个可以继续深挖的方向如果你对 Morris 遍历有兴趣建议去把 Morris 的前序和后序遍历也自己推一遍。前序的线索挂载点、后序的逆序输出方式和中序的区别比想象中要大自己推一遍比看十遍题解都管用。或者你可以试试给 LC.99 加一个变体如果是二叉搜索树中有 k 个节点被交换了怎么定位它们思路会完全不一样但理解 LC.99 的细节之后你会知道为什么两个节点被交换这个限制如此精妙——它让解法收敛到极致简洁。我自己刷完这道题后的体会是不要因为代码短就低估它的价值。LC.99 的高频出现恰恰因为它把 BST 性质、中序遍历、指针技巧、空间优化这些考点全串在了一个小题里每一层都有东西可以挖。把它吃透比囫囵吞枣刷十道树的题目都有用。