刷题的朋友应该对“LC.99 恢复二叉搜索树”不陌生。这道题表面上只给了个二叉搜索树BST说有两个节点的值被错误交换了要求恢复这棵树。很多人第一反应是“中序遍历一次找到异常点交换回来”但真动手写的时候容易在“到底哪两个点”和“如何用常数空间遍历”上卡住。这篇文章我就把中序遍历这条主线彻底拆开从暴力解法一路讲到 Morris 遍历把定位逻辑、代码细节、边界情况都过一遍希望能帮你把这题吃透。这道题非常适合准备算法面试的人、正在刷树相关题目的朋友以及那些觉得“ BFS/DFS 已经够用但想挑战常数空间”的学习者。它考的不只是“你会不会中序遍历”而是你对性质的理解和代码实现中的严谨度。1. 题目拆解与核心思路为什么突破口一定是中序遍历1.1 一句话讲清楚题目在做什么给定一棵 BST其中恰好两个节点的值被错误地交换了。要求不改变树的结构只通过交换这两个节点的值让整棵树重新满足 BST 性质。比如正确的 BST 中序遍历可能是[1,2,3,4]错误交换后变成[1,3,2,4]你要做的就是定位到 3 和 2把值换回来。注意题目隐含了一个约束不改变结构。也就是说你不能把节点删掉重建也不能改变父子关系只能交换值。很多人会问那直接把中序遍历序列重新排序后回填行不行可以这是最容易想到的思路但进阶要求是尝试用 O(1) 的空间复杂度完成。这就逼着你深入理解中序遍历和 BST 性质。1.2 为什么“中序序列是递增的”能当解题钥匙BST 的核心定义是左子树的所有节点值都小于根节点值右子树的所有节点值都大于根节点值。这个定义直接引出一个重要推论对 BST 做中序遍历得到的序列一定是严格递增的。反过来思考如果一棵树自称是 BST但中序遍历结果不是递增的那么它一定不满足 BST 性质。而题目告诉我们只是两个节点的值被错误交换所以中序遍历的结果中必然出现“局部递减”的异常现象。这里我用一个生活类比帮助理解把 BST 的中序序列看成一排按身高从矮到高排队的人。中间不小心让两个人互换位置队伍里就会出现“高个子挡在矮个子前面”的乱序。我们要做的事就是通过观察这些乱序锁定是哪两个人换了位置。所以这道题的核心思路非常清晰中序遍历 BST找到破坏递增性的两个节点交换它们的值。难的点在于如何准确找到这两个节点以及如何让遍历过程不占用额外空间。2. 从暴力解法到 O(1) 空间三种方案的演进逻辑2.1 方案一中序数组排序回填最直观但不优雅最直接的实现是先中序遍历整棵树把所有节点值记录到一个数组里。然后对这个数组排序得到正确的递增序列。接着再中序遍历一次把排序后的值按顺序填回各个节点。这个方法思路简单代码也好写但存在两个明显问题时间复杂度是 O(n log n)因为要排序。空间复杂度是 O(n)因为要存储节点值和数组。其实仔细观察会发现排序本身不是必须的。因为错误交换只会导致两个节点异常正确序列和错误序列之间的差异很小。如果先得到错误中序数组再和排序后的数组逐位比较也能定位出两个位置但本质上仍然需要额外数组。2.2 方案二一次遍历定位两个异常节点这才是正道既然中序序列本身就能反映异常为什么要排序呢我们可以直接在一次中序遍历过程中维护一个“前驱节点”指针 prev比较 prev.val 和当前节点 cur.val。正常情况下prev.val cur.val。一旦出现 prev.val cur.val就说明找到了一个逆序对。这里的关键结论是第一个逆序对的前一个节点prev一定是两个错误节点中的“较大值”之一。如果只有一个逆序对那么第二个错误节点就是这个逆序对中的当前节点cur。如果有两个逆序对那么第二个错误节点是第二个逆序对中的当前节点cur。先用数学直觉理解一下。原始正确序列是[1,2,3,4,5,6]。假设交换了 2 和 5得到[1,5,3,4,2,6]。此时出现了两次逆序第一次是53第二次是42。第一次逆序的前一个节点 5 是错误节点之一最后一次逆序的后一个节点 2 是另一个错误节点。再假设交换的是相邻的 3 和 4得到[1,2,4,3,5,6]只有一次逆序43。前一个节点 4 是错误节点当前节点 3 也是错误节点。所以算法逻辑可以统一为用一个变量 first 记录第一次逆序时的 prev用 second 在每次出现逆序时都更新为当前节点 cur。遍历结束后只需交换 first.val 和 second.val。为什么 second 要“每次都被覆盖”因为如果只有一个逆序对second 就是这个逆序对的 cur如果有两个逆序对second 需要被更新为第二次逆序对的 cur。这个细节是很多人写错的地方后面我会专门展开。2.3 方案三Morris 遍历把空间真正压到常数级递归中序遍历的额外空间是 O(h)h 是树高最坏情况下是 O(n)。迭代中序遍历用显式栈空间同样是 O(n)。如果题目要求 O(1) 空间就必须使用 Morris 遍历。Morris 遍历的核心思想是利用叶子节点的空右指针把当前节点的中序前驱临时“接到”当前节点身上形成一条临时线索。这样遍历完左子树后就能通过这个线索回到当前节点而不需要栈来保存回溯路径。我简单描述 Morris 中序遍历的流程初始化 cur root。如果 cur.left 不存在访问 cur然后 cur cur.right。如果 cur.left 存在找到 cur 左子树中最右的节点 predecessor即中序前驱。如果 predecessor.right 为空说明还没挂线就把 predecessor.right 指向 cur然后 cur cur.left继续深入左子树。如果 predecessor.right 已经指向 cur说明左子树已经遍历完这就是“拆线”的时机把 predecessor.right 恢复为 null访问 cur然后 cur cur.right。在第 5 步访问 cur 时正好可以执行“比较前驱和当前节点”的操作。整个过程中除了几个指针变量外没有使用额外存储空间复杂度是 O(1)。把三种方案放在一起对比演进逻辑就清楚了方案时间空间代码复杂度适用场景中序数组排序回填O(n log n)O(n)低快速拿到一个能跑的答案一次遍历定位O(n)O(h) 或 O(n)中面试常规推荐方案Morris 遍历O(n)O(1)高追求极致空间复杂度3. 核心代码实现与关键细节解析3.1 递归版最容易理解也最容易写错 prev 更新时机先看递归版完整实现Python因为代码简洁适合演示class Solution: def recoverTree(self, root: Optional[TreeNode]) - None: first second None prev None def inorder(node): nonlocal first, second, prev if not node: return inorder(node.left) # 访问当前节点比较 prev.val 和 node.val if prev and prev.val node.val: if first is None: first prev second node prev node # 关键访问完当前节点后再更新 prev inorder(node.right) inorder(root) first.val, second.val second.val, first.val这段代码里有三个容易写错的地方prev node必须放在“访问当前节点”之后而不是进入节点时。如果放在递归左子树前更新那 prev 就不是严格意义上的中序前驱了。first只在第一次遇到逆序时赋值而且赋的是prev不是node。second每次逆序都要更新为node不能只在第一次赋值。再看 C 递归版class Solution { public: TreeNode *first nullptr, *second nullptr, *prev nullptr; void recoverTree(TreeNode* root) { inorder(root); swap(first-val, second-val); } void inorder(TreeNode* node) { if (!node) return; inorder(node-left); if (prev prev-val node-val) { if (!first) first prev; second node; } prev node; inorder(node-right); } };C 版利用成员变量在递归函数之间共享状态逻辑和 Python 是一致的。只要记住核心三行代码语言其实不重要。3.2 迭代版用显式栈替代系统调用栈递归版虽然好理解但有一个隐患如果树退化成链状递归深度可能非常大导致栈溢出。迭代版用显式栈把空间消耗从系统栈转移到堆上更可控。class Solution: def recoverTree(self, root: Optional[TreeNode]) - None: first second None prev None stack [] cur root while stack or cur: while cur: stack.append(cur) cur cur.left cur stack.pop() # 核心定位逻辑 if prev and prev.val cur.val: if first is None: first prev second cur prev cur cur cur.right first.val, second.val second.val, first.val迭代版就是在标准中序迭代遍历的“出栈访问”环节加入了定位逻辑。这个版本的空间复杂度是 O(h)h 为树高最坏 O(n)但比递归更稳。3.3 Morris 版挂线与拆线的时机必须精确Morris 版最容易让人困惑的点在于“什么时候访问节点”“什么时候挂线”“什么时候拆线”。我按照代码顺序逐步解释。class Solution: def recoverTree(self, root: Optional[TreeNode]) - None: first second None prev None def visit(node): nonlocal first, second, prev if prev and prev.val node.val: if first is None: first prev second node prev node cur root while cur: if not cur.left: visit(cur) cur cur.right else: pred cur.left while pred.right and pred.right ! cur: pred pred.right if pred.right is None: # 第一次到达挂线索然后深入左子树 pred.right cur cur cur.left else: # 第二次到达说明左子树遍历完毕先拆线索再访问当前节点 pred.right None visit(cur) cur cur.right first.val, second.val second.val, first.val关键点全在 while 循环的else分支里第一次找到pred.right为空执行pred.right cur这是挂线索。注意此时不访问 cur而是让 cur 去左子树。当 cur 从左子树回来时再次走到同一位置这时pred.right已经等于 cur说明左子树走完了。先执行pred.right None拆线索再访问 cur然后进入右子树。为什么要先拆线因为如果不把pred.right改回null树结构就被永久改了后面别的遍历逻辑会出问题。更重要的是拆线之后pred.right恢复原状才不会破坏 BST 的原有结构。另外注意一个隐藏问题如果树中有节点本身就没有右子树那pred.right cur这个操作是安全的但如果某个节点原本就有右子树而它的中序前驱不是它左子树的最右节点吗正好左子树最右节点的右指针一定为空所以这个挂线操作永远不会覆盖原本存在的右子树。这就是 Morris 遍历正确性的底层保证。4. 手工推演用一棵坏树完整走一遍定位流程4.1 构造用例相邻交换的情况假设一棵正确的 BST 经过交换后长这样3 / \ 1 4 / 2错误交换发生在 2 和 3 之间。我们看一下中序遍历结果中序序列[1, 3, 2, 4]只看序列会发现只有一处逆序3 2。按照算法逻辑遍历到 1prev 从空变为 1。遍历到 3prev.val 1 3正常prev 更新为 3。遍历到 2prev.val 3 2逆序出现。first 为空所以 first prev 3second 当前节点 2。遍历到 4prev.val 2 4正常prev 更新为 4。结束后 first 3second 2。交换这两个节点的值树变成2 / \ 1 4 / 3中序序列变为[1, 2, 3, 4]恢复成功。注意交换的是值不是节点结构所以树的形状没有变。4.2 构造用例不相邻交换的情况再构造一个更复杂的例子。原正确 BST 中序序列是[1, 2, 3, 4]交换根节点 2 和右子树中的 4得到树4 / \ 1 2 / 3中序遍历结果为[1, 4, 3, 2]。观察序列出现了两处逆序4 33 2算法流程遍历到 1正常。遍历到 4prev.val 1 4正常prev 更新为 4。遍历到 3发现4 3第一次逆序。first 4second 3。遍历到 2发现3 2第二次逆序。first 保持不变second 更新为 2。最后 first 4second 2。交换后中序是[1, 2, 3, 4]树结构不变。看到了吗中间那个 3 在序列里形成了两次逆序但它本身不是错误节点它只是被夹在两个错误节点之间。所以 second 必须持续更新到最后一次逆序的当前节点这样就能直接取到真正错误的节点 2。这个例子非常关键建议不理解的朋友用笔在纸上把树画出来再按中序顺序手动走一遍 prev 指针一次就能想明白。5. 常见错误与排查实录5.1 最容易踩的四个坑坑一只记录第一个逆序对的两个节点第二处逆序被忽略有些初学者会把逻辑写成“遇到第一个逆序对直接 first prev second node然后 break”。这在相邻交换时是没问题的因为只有一处逆序。但遇到不相邻交换就会出现[1,4,3,2]这种情况如果只取第一个逆序对会得到 first 4second 3交换后变成[1,3,4,2]问题依然存在。记牢这个规则first 只在第一次赋值second 每次都覆盖。坑二prev 的更新顺序不对递归版里如果写成def inorder(node): if not node: return prev node # 错误在遍历左子树前就更新 inorder(node.left) # ...那中序遍历的 prev 就不是严格前驱了比较结果会完全错乱。务必保证“先遍历左子树再访问节点并更新 prev再遍历右子树”。坑三Morris 遍历忘记判断 pred.right ! cur导致死循环在寻找中序前驱时如果写的是while pred.right: pred pred.right那么第一次挂线后pred.right 指向 cur下次再到达同一节点时while 循环会一路走到没有右子树的叶子节点肯定不会回到 cur逻辑直接崩溃。正确写法必须是while pred.right and pred.right ! cur: pred pred.right这是 Morris 能“走出去又走回来”的关键。坑四忽略 first 为空时的 second 初始化有的写法是if prev.val node.val: if first is None: first prev second node else: second node这其实是错的。因为如果只有一次逆序第二个错误节点是 node没问题但如果有两次逆序第二次逆序时 first 已经不是 None会走 else 分支更新 second最后结果也正确。真正有问题的是另一种写法if prev.val node.val: if first is None: first prev second prev # 错误把 second 也指向 prev这样第一次逆序时 second 变成了 prev而不是 node。单逆序时结果就错了。正确写法是把 second 赋值从 if 中提出来每次逆序都执行second node。5.2 边界条件与极端情况速查表情况结果说明空树直接返回first 和 second 都为空需要判空只有一个节点直接返回没有逆序逻辑自动跳过树退化成链表递归版可能栈溢出用迭代版更安全两个错误节点都在最深层叶子正常定位中序遍历一定能访问到所有节点交换的是根节点和叶子正常定位根节点可能作为 first 出现还有一个小提醒很多语言在实现时需要把 first、second、prev 定义为成员变量或使用闭包否则递归函数里无法更新外层变量。Python 用nonlocalJava 用成员变量C 用类成员或引用传递各有各的写法但思路一样。5.3 面试答题的节奏建议如果面试遇到这道题我建议这样组织回答先讲 BST 中序遍历递增的性质给出暴力方案O(n) 空间排序回填证明你思路是通的。再讲优化一次遍历定位两个异常节点解释 first / second 的赋值逻辑。最后主动提 Morris 遍历重点说明如何用规则指针实现 O(1) 空间的回溯。如果时间有限第三部分可以只讲思路、不手写但要能把“挂线、拆线、访问节点”三步说清楚。面试官大概率会追问“如果交换了两次会怎么样”这类变式只要你把 first 和 second 的更新逻辑讲透了变式不是问题。结尾一点个人体会我自己最初刷这题时也犯过“只记录第一个逆序对”的错误当时对着[1,4,3,2]这个用例调了半天才意识到 second 需要每次都更新。后来我总结了一个土办法把中序序列写出来把错误交换的两个值标红然后观察它们周围的逆序关系比直接看树结构直观得多。另外Morris 遍历对于理解二叉树线索化的思想很有帮助建议即使面试不需要也抽时间把它写熟练。这道题的收获不止于“会做一道题”它还能帮你把中序遍历、BST 性质、空间复杂度优化串成一条完整的知识链以后再遇到类似的“找异常节点”问题思路会快很多。