企业官网建设流程全解析

刷题的朋友应该对“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]。此时出现了两次逆序：第一次是5>3，第二次是4>2。第一次逆序的前一个节点 5 是错误节点之一，最后一次逆序的后一个节点 2 是另一个错误节点。

再假设交换的是相邻的 3 和 4，得到[1,2,4,3,5,6]，只有一次逆序：4>3。前一个节点 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 中序遍历的流程：

1. 初始化 cur = root。
2. 如果 cur.left 不存在，访问 cur，然后 cur = cur.right。
3. 如果 cur.left 存在，找到 cur 左子树中最右的节点 predecessor（即中序前驱）。
4. 如果 predecessor.right 为空，说明还没挂线，就把 predecessor.right 指向 cur，然后 cur = cur.left，继续深入左子树。
5. 如果 predecessor.right 已经指向 cur，说明左子树已经遍历完，这就是“拆线”的时机：把 predecessor.right 恢复为 null，访问 cur，然后 cur = cur.right。

在第 5 步访问 cur 时，正好可以执行“比较前驱和当前节点”的操作。整个过程中，除了几个指针变量外，没有使用额外存储，空间复杂度是 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。按照算法逻辑：

• 遍历到 1，prev 从空变为 1。
• 遍历到 3，prev.val = 1 < 3，正常，prev 更新为 3。
• 遍历到 2，prev.val = 3 > 2，逆序出现。first 为空，所以 first = prev = 3；second = 当前节点 = 2。
• 遍历到 4，prev.val = 2 < 4，正常，prev 更新为 4。

结束后 first = 3，second = 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 > 3
• 3 > 2

算法流程：

• 遍历到 1，正常。
• 遍历到 4，prev.val = 1 < 4，正常，prev 更新为 4。
• 遍历到 3，发现4 > 3，第一次逆序。first = 4，second = 3。
• 遍历到 2，发现3 > 2，第二次逆序。first 保持不变，second 更新为 2。

最后 first = 4，second = 2。交换后中序是[1, 2, 3, 4]，树结构不变。看到了吗？中间那个 3 在序列里形成了两次逆序，但它本身不是错误节点，它只是被夹在两个错误节点之间。所以 second 必须持续更新到最后一次逆序的当前节点，这样就能直接取到真正错误的节点 2。

这个例子非常关键，建议不理解的朋友用笔在纸上把树画出来，再按中序顺序手动走一遍 prev 指针，一次就能想明白。

5. 常见错误与排查实录

5.1 最容易踩的四个坑

坑一：只记录第一个逆序对的两个节点，第二处逆序被忽略

有些初学者会把逻辑写成“遇到第一个逆序对，直接 first = prev， second = node，然后 break”。这在相邻交换时是没问题的，因为只有一处逆序。但遇到不相邻交换就会出现[1,4,3,2]这种情况，如果只取第一个逆序对，会得到 first = 4，second = 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、prev 定义为成员变量或使用闭包，否则递归函数里无法更新外层变量。Python 用nonlocal，Java 用成员变量，C++ 用类成员或引用传递，各有各的写法，但思路一样。

5.3 面试答题的节奏建议

如果面试遇到这道题，我建议这样组织回答：

1. 先讲 BST 中序遍历递增的性质，给出暴力方案（O(n) 空间排序回填），证明你思路是通的。
2. 再讲优化：一次遍历定位两个异常节点，解释 first / second 的赋值逻辑。
3. 最后主动提 Morris 遍历，重点说明如何用规则指针实现 O(1) 空间的回溯。

如果时间有限，第三部分可以只讲思路、不手写，但要能把“挂线、拆线、访问节点”三步说清楚。面试官大概率会追问“如果交换了两次会怎么样”这类变式，只要你把 first 和 second 的更新逻辑讲透了，变式不是问题。

结尾：一点个人体会

我自己最初刷这题时，也犯过“只记录第一个逆序对”的错误，当时对着[1,4,3,2]这个用例调了半天才意识到 second 需要每次都更新。后来我总结了一个土办法：把中序序列写出来，把错误交换的两个值标红，然后观察它们周围的逆序关系，比直接看树结构直观得多。另外，Morris 遍历对于理解二叉树线索化的思想很有帮助，建议即使面试不需要，也抽时间把它写熟练。这道题的收获不止于“会做一道题”，它还能帮你把中序遍历、BST 性质、空间复杂度优化串成一条完整的知识链，以后再遇到类似的“找异常节点”问题，思路会快很多。