LeetCode 99. 恢复二叉搜索树

2026-06-03 HGNULB 约 5 分钟

文章信息 11 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 10-20 字节跳动微软猿辅导华为拼多多图森

题目描述

✅ 99. 恢复二叉搜索树

题意分析

给一棵本来合法的二叉搜索树，其中恰好有两个节点的值被互相交换了，要求把这两个值换回去，让它重新成为一棵二叉搜索树。

「恰好两个」是最关键的约束信号：不是若干个错位，也不是任意打乱，而是一次对换。这意味着错误是成对出现的，找到这一对就够了，不需要排序整棵树。

另一个约束是不能改变树的结构。所以能动的只有节点里存的值，指针一律不碰。

要输出的东西很轻——没有返回值，直接原地修改。真正的难点在于「怎么在树形结构里认出这两个被换过的节点」。

边界情况有三类：两个被换的节点在中序序列里相邻；它们相隔很远；以及树很小，比如只有两三个节点。这三类要用同一套判断覆盖。

解法：中序遍历定位两个逆序节点

核心思路

二叉搜索树的中序序列严格递增。两个节点值被交换后，问题就变成：在一个原本递增的序列中，找出被交换的两个元素。

扫描中序序列并比较相邻节点 prev、cur。一旦出现 prev.val > cur.val：

第一次逆序的前者一定是较大的错误节点，记为 first。

每次逆序的后者都更新为 second。

若两个错误值相邻，只出现一次逆序，此时这一对正好就是答案；若不相邻，会出现两次逆序，first 保留第一次的前者，second 最终成为第二次的后者。例如 1,4,3,2,5 中应取 4 和 2。

不变量是：已访问前缀中，first 始终是第一处逆序的前者，second 始终是最近一处逆序的后者。一次交换最多制造这两处边界异常，因此遍历结束后交换两者的值即可恢复全局递增；树的指针结构无需改动。

解题步骤

用显式栈迭代执行中序遍历，prev 保存上一个访问节点。

当 prev.val > cur.val 时发现逆序：若 first 为空就记录 prev，并总是把 second 更新为 cur。

更新 prev = cur，继续遍历右子树。

遍历完成后交换 first.val 与 second.val。

对中序序列 3,2,1，先发现 3 > 2，得到 first = 3, second = 2；再发现 2 > 1，只把 second 更新为 1。最后交换 3 和 1，序列恢复为 1,2,3。

代码实现

import java.util.ArrayDeque;
import java.util.Deque;

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
}

复杂度分析

时间复杂度：$O(n)$，每个节点入栈、出栈各一次。

空间复杂度：$O(h)$，其中 $h$ 是树高；平衡树为 $O(\log n)$，最坏退化为 $O(n)$。

关键点总结

BST 中序有序是把树问题转成数组逆序问题的桥梁。

统一规则是“第一次逆序取前者，每次逆序取后者”。

相邻交换产生一处逆序，不相邻交换通常产生两处逆序，同一段代码都能处理。

题目要求保持树结构，所以只交换节点值。

若面试追问 $O(1)$ 额外空间，可把中序遍历替换为 Morris 遍历，错误节点的识别逻辑不变。

易错点总结

发现第一处逆序就交换，会在错误节点不相邻时选错 second。

每次逆序都覆盖 first，会丢失真正较大的错误节点。

等待第二处逆序才设置 second，会漏掉相邻交换。

忘记判断 prev != null，访问第一个节点时会空指针。

交换节点指针而非节点值，会无谓地破坏原树结构。

相似题目

题目	难度	考察点
98. 验证二叉搜索树	中等	判定中序是否递增
94. 二叉树的中序遍历	简单	中序遍历模板
230. 二叉搜索树中第 K 小的元素	中等	中序取第 K 个
501. 二叉搜索树中的众数	简单	中序统计相等段
783. 二叉搜索树节点最小距离	简单	中序相邻差值
173. 二叉搜索树迭代器	中等	中序遍历拆成迭代器