LeetCode 99. 恢复二叉搜索树
题目描述
题意分析
原本合法的二叉搜索树中，恰好两个节点的值被交换了，需要把它恢复为合法的二叉搜索树。节点和左右孩子连接都要保留，只交换错误节点的值。
二叉搜索树的中序遍历按数值递增，因此可以利用访问顺序定位被交换的两个值。题目还要求思考常数额外空间的进阶做法，下面先用显式栈说明定位规则，再用 Morris 遍历消除栈空间。
解法：中序遍历定位两个逆序节点
核心思路
[!blue]
正常的中序序列严格递增，交换两个值之后，只有它们附近的顺序会受到影响。用
prev保存刚访问过的节点，若prev.val > cur.val，就发现了一处相邻下降。设被交换的两个原值一小一大。大值被放到前面后，会在某处成为下降的前一个元素；小值被放到后面后，会成为下降的后一个元素。两节点在中序中相邻时，这两种现象合并成同一处下降；不相邻时，则分别表现为两处下降。
所以可以使用统一规则：首次发现下降时，把前一个节点记录为
first，之后不再覆盖；每次发现下降时，把当前节点记录为second。扫描结束后，first是错放到前面的大值节点，second是错放到后面的小值节点，交换它们即可恢复顺序。用显式栈实现中序访问：先沿左孩子不断入栈，取出栈顶作为当前节点，再转向它的右子树。栈保存的是左子树尚未访问完、之后还需要返回的祖先；不需要保存完整中序数组。
必须先完成定位再交换。如果第一处下降就立刻修正，两个错误节点不相邻时，当前的
second还不是最终目标。题目保证恰好两个节点值交换，因此遍历后一定能找到待交换节点。
解题步骤
- 初始化空栈、当前节点
cur，以及空的prev、first、second。- 沿左孩子入栈，直到没有左侧节点，然后弹出栈顶进行中序访问。
- 若与
prev构成下降，首次记录first = prev，每次更新second = cur。- 令
prev = cur，转向当前节点的右子树，继续中序遍历。- 遍历结束后交换
first.val与second.val，不修改节点连接。
代码实现
class Solution {
public void recoverTree(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
TreeNode prev = null;
TreeNode first = null;
TreeNode second = null;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (prev != null && prev.val > cur.val) {
// 较大的错误节点取第一次下降的前者，只记录一次。
if (first == null) {
first = prev;
}
// 较小的错误节点取最后一次下降的后者。
second = cur;
}
prev = cur;
cur = cur.right;
}
int value = first.val;
first.val = second.val;
second.val = value;
}
}
func recoverTree(root *TreeNode) {
stack := make([]*TreeNode, 0)
cur := root
var prev, first, second *TreeNode
for cur != nil || len(stack) > 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if prev != nil && prev.Val > cur.Val {
// 较大的错误节点取第一次下降的前者，只记录一次。
if first == nil {
first = prev
}
// 较小的错误节点取最后一次下降的后者。
second = cur
}
prev = cur
cur = cur.Right
}
first.Val, second.Val = second.Val, first.Val
}
复杂度分析
设节点数为 $n$，树高为 $h$。
- 时间复杂度：$O(n)$，每个节点入栈、出栈各一次。
- 辅助空间复杂度：$O(h)$，显式栈保存当前祖先路径；平衡树为 $O(\log n)$，最坏为 $O(n)$。
关键点总结
[!green]
- 中序递增把恢复树转成定位有序序列中两个错放的值。
first只取首次下降的前者，second取最后一次下降的后者。- 同一规则覆盖相邻和不相邻交换，最终只交换节点值。
解法二：Morris 中序遍历
核心思路
[!blue]
显式栈的作用是在走完左子树后找到回来的路。Morris 利用左子树中序最后一个节点的空右指针，临时连回当前节点，以这条线索代替栈；对外保留的树结构在遍历结束前全部恢复。
对当前节点
cur，若没有左孩子，就可以直接中序访问它，再转向右侧。若有左孩子，则在左子树中沿右指针找到最右节点predecessor，它就是当前节点的中序前驱：
- 前驱右指针为空，说明第一次到达
cur。把该右指针临时指向cur，然后进入左子树，此时还不能访问cur。- 前驱右指针已经指向
cur，说明左子树已经走完，并沿线索回来了。先清除这条临时连接，再访问cur，然后进入右子树。寻找前驱时遇到指回
cur的连接就停止，不能继续沿它搜索。两种情况区分了“准备进入左子树”和“左子树处理完成”，从而保持真正的中序顺序，每个节点只在正确时机被访问一次。每次中序访问仍使用上一解法的
prev、first、second定位下降。遍历必须完整结束，即使已经找到两个错误节点也继续清理剩余线索；最后再交换两节点值。临时修改的只有原本为空的前驱右指针，并且每条都会被清除，最终树的左右孩子关系保持原样。
解题步骤
- 初始化
cur = root，以及空的prev、first、second。- 若当前节点有左子树，寻找其最右节点作为中序前驱。
- 前驱右指针为空时，建立返回线索，转入左子树并继续循环；已经指回当前节点时，清除线索。
- 对无左子树或刚完成左子树的当前节点，比较
prev，按首次前者、末次后者的规则记录错误节点。- 更新
prev并转向右侧，直到遍历结束、所有线索恢复，再交换错误节点值。
代码实现
class Solution {
public void recoverTree(TreeNode root) {
TreeNode cur = root;
TreeNode prev = null;
TreeNode first = null;
TreeNode second = null;
while (cur != null) {
if (cur.left != null) {
TreeNode predecessor = cur.left;
while (predecessor.right != null && predecessor.right != cur) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
predecessor.right = cur;
cur = cur.left;
continue;
}
predecessor.right = null;
}
if (prev != null && prev.val > cur.val) {
if (first == null) {
first = prev;
}
second = cur;
}
prev = cur;
cur = cur.right;
}
int value = first.val;
first.val = second.val;
second.val = value;
}
}
func recoverTree(root *TreeNode) {
cur := root
var prev, first, second *TreeNode
for cur != nil {
if cur.Left != nil {
predecessor := cur.Left
for predecessor.Right != nil && predecessor.Right != cur {
predecessor = predecessor.Right
}
if predecessor.Right == nil {
predecessor.Right = cur
cur = cur.Left
continue
}
predecessor.Right = nil
}
if prev != nil && prev.Val > cur.Val {
if first == nil {
first = prev
}
second = cur
}
prev = cur
cur = cur.Right
}
first.Val, second.Val = second.Val, first.Val
}
复杂度分析
设节点数为 $n$。
- 时间复杂度：$O(n)$。每条前驱线索只建立、清除一次，寻找前驱涉及的右链也只被经过常数次，总遍历量为线性。
- 辅助空间复杂度：$O(1)$。不使用递归或显式栈，只维护常数个节点指针。
关键点总结
[!green]
- 用中序前驱的空右指针暂存返回路线，消除祖先栈。
- 建线后先处理左子树，拆线后才访问当前节点。
- 错误节点定位规则不变，完整遍历后所有临时连接都恢复。
易错点总结
[!yellow]
- 首次下降就交换，会在两个错误节点不相邻时选错后一个目标。
- 每次下降都覆盖
first会丢失错放的大值；只在第二次下降设置second又会漏掉相邻交换。- 访问第一个节点时
prev为空，应先判空再比较；不要用普通整数哨兵代替节点，因为合法值可以达到整数边界。- 交换的是两个节点的值，不是节点对象或左右孩子。
- Morris 中找到两个错误节点后也不能提前返回，必须继续走完，把所有临时前驱连接恢复为空。
- Morris 寻找前驱时要同时检查右指针是否为空、是否已经指回当前节点，否则会沿临时连接无限循环。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 98. 验证二叉搜索树 | 中等 | 同样利用BST中序严格递增，本题还要找出并交换造成逆序的两个节点值。 |
| 94. 二叉树的中序遍历 | 简单 | 中序遍历提供访问顺序，配合前一节点即可定位异常顺序。 |
| 补充题 215. 二叉搜索树中被交换的两个节点值 | 中等 | 都利用中序遍历中的逆序位置定位错误节点；补充题返回两个值。 |
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 通过中序访问利用二叉搜索树的升序性质；本题根据下降位置定位交换节点，该题在第 k 次访问时取值。 |
| 173. 二叉搜索树迭代器 | 中等 | 通过中序访问利用二叉搜索树的升序性质；本题根据下降位置定位交换节点，该题用栈保存尚未访问的后续节点。 |
| 530. 二叉搜索树的最小绝对差 | 简单 | 通过中序访问利用二叉搜索树的升序性质；本题根据下降位置定位交换节点，该题比较相邻中序值的差。 |