如何恢复一棵被错误交换了两个节点的二叉搜索树？

简化版

BST 中序遍历本应严格升序，如果有两个节点的值被交换了，中序序列里就会出现逆序对（前面的比后面的大）。做一次中序遍历找出这两个「错位」的节点，把它们的值交换回来即可。关键：相邻交换会产生 1 个逆序对，非相邻交换会产生 2 个逆序对，要正确识别出被交换的两个节点。

详细版

正常 BST 中序是升序，如 1 2 3 4。交换其中两个节点后会破坏升序：

交换相邻两个（如 1 3 2 4）：出现 1 处逆序（3 > 2）。要交换的就是这一对 3 和 2。
交换非相邻两个（如 3 2 1 由 1 2 3 交换首尾得来，序列 3 2 1）：出现 2 处逆序（3>2、2>1）。要交换的是第一处逆序的较大者和第二处逆序的较小者。

TreeNode first = null, second = null, prev = null;
void recoverTree(TreeNode root) {
    inorder(root);
    int t = first.val; first.val = second.val; second.val = t;  // 换回来
}
void inorder(TreeNode cur) {
    if (cur == null) return;
    inorder(cur.left);
    if (prev != null && prev.val > cur.val) {   // 发现逆序对 (prev, cur)
        if (first == null) first = prev;        // 第一处逆序：记较大者 prev
        second = cur;                           // 每处逆序都更新较小者 cur
    }
    prev = cur;
    inorder(cur.right);
}

first 只在第一次遇到逆序时记 prev（较大者）；second 每次都更新为 cur（较小者）。这样两种情况都能正确定位。

完整版教学

一、把问题转化为「中序序列找错位」

BST ⟺ 中序升序。既然题目说「两个节点被交换」，那这棵树的中序遍历一定不再是完全升序，而是「一个升序序列里两个数被调换了位置」。所以问题变成：在一个几乎升序、只有两处错位的序列里，找出这两个被换的数。 找到后交换它们的值就恢复了。（题目通常只要求换值，不必真的移动节点。）

二、为什么看逆序对的数量

一个升序序列被交换两个元素后，逆序对（前一个 > 后一个）的数量取决于这两个元素是否相邻：

相邻交换，如 1 [3 2] 4：只在这两个数之间产生 1 个逆序对。被交换的就是这一对。
非相邻交换，如 [3] 2 [1]（原 1 2 3 换了首尾）：产生 2 个逆序对（3>2 和 2>1）。被交换的两个数是——第一个逆序对里靠前的大数（3）和第二个逆序对里靠后的小数（1）。

三、first 和 second 的记录规则（核心）

统一的处理方式，遍历中每遇到逆序对 (prev, cur)（即 prev.val > cur.val）：

first（要换的较大者）只记第一次：if (first == null) first = prev;。相邻情况它就是唯一逆序对的 prev；非相邻情况它是第一个逆序对的 prev。
second（要换的较小者）每次都更新：second = cur;。相邻情况它是唯一逆序对的 cur；非相邻情况它会先被第一个逆序对设成中间值、再被第二个逆序对更新成最终的小数。

这套规则同时覆盖相邻和非相邻两种情况，不用分别写。

四、走两个例子验证

例1（相邻）中序: 1 3 2 4
  遇到 (3,2) 逆序: first=3（第一次记）, second=2
  交换 3 和 2 → 恢复 1 2 3 4 ✓

例2（非相邻）中序: 3 2 1
  遇到 (3,2) 逆序: first=3, second=2
  遇到 (2,1) 逆序: first 已有不变, second=1
  交换 3 和 1 → 恢复 1 2 3 ✓

五、复杂度与优化

时间 O(n)：一次中序遍历。
空间 O(h)：递归栈。用 Morris 中序遍历可做到 O(1) 额外空间——这也是本题的进阶考点（面试官常追问「能否常数空间」，答案就是 Morris）。

六、常见误区与追问

考点	正确口径
相邻交换	中序序列出现 1 个逆序对
不相邻交换	中序序列出现 2 个逆序对
修复动作	交换 first 和 second 的值，不重连结构

if prev.val > cur.val:
  if first == null: first = prev
  second = cur
swap(first.val, second.val)

恢复 BST 的核心是看中序序列里的逆序，而不是在树结构上猜哪两个节点错了。

误区：需要重新构建整棵 BST。 题目通常只交换了两个节点的值，结构仍在；找出两个值再交换回来即可。
误区：只记录第一次逆序的两个节点。 不相邻交换会出现两次逆序，第二个错误节点要更新为第二次逆序里的当前节点。
误区：比较当前节点和父节点就能发现错误。 BST 的全局顺序体现在中序序列中，父子局部比较不够可靠。
追问：相邻交换如何处理？ 只出现一次逆序，first=prev、second=cur，最后交换两者。
追问：空间复杂度能优化吗？ 普通中序递归 O(h)，Morris 中序可以 O(1) 额外空间，但实现更绕。
追问：为什么只交换值不交换节点？ 交换节点指针会涉及父子关系和多种结构边界；题目要求恢复值顺序时交换值更简单。

七、加强记忆

恢复被交换两节点的 BST：中序遍历本应升序，交换会产生逆序对——相邻交换 1 个、非相邻交换 2 个。遍历中维护 prev，遇逆序对 (prev,cur) 时：first 只记第一次的 prev（大者）、second 每次都更新为 cur（小者），这套规则同时覆盖两种情况；最后交换 first、second 的值。O(n)，Morris 可 O(1) 空间。

简化版

详细版