解法)
刷题刷到 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(k+1)。这说明交换就发生在ak和a(k+1)这两个相邻元素之间。我们的代码在遍历到a(k+1)时会检测到降序，此时prev就是ak，current就是a(k+1)。first = ak，second = a(k+1)，正好就是这两个错误节点，后续不会再触发别的降序。
情形二：序列中有两处降序，即在位置p和位置q处（p < q），分别有ap > a(p+1)和aq > a(q+1)。这种情况的本质是被交换的两个元素相距较远：较大的那个被放到了ap位置，较小的那个被放到了a(q+1)位置。代码在位置p处第一次触发降序，first = ap；在位置q处第二次触发降序，second被覆盖成a(q+1)。最终first = ap，second = a(q+1)，恰好是那两个被交换的节点。
所以你看，这个写法的妙处在于它不需要记录"这是第几次降序"，只需要把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的父节点指向second，second的父节点指向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 性质、中序遍历、指针技巧、空间优化这些考点全串在了一个小题里，每一层都有东西可以挖。把它吃透，比囫囵吞枣刷十道树的题目都有用。
