京公网安备11010502063487号给定一棵二叉搜索树，其中恰好有两个结点的值被错误地交换了，要求在不改变树结构的情况下恢复它。关键观察：二叉搜索树的中序遍历是严格递增的。两个结点的值被交换后，中序序列里会出现"前一个比后一个大"的逆序对：如果被交换的两个结点在中序里不相邻，会有两个逆序对，需要交换的是第一个逆序对里较大的那个和第二个逆序对里较小的那个；如果它们在中序里恰好相邻，就只有一个逆序对，交换的就是这一对本身。所以做法是做一次中序遍历，记录 first 和 second，最后交换它们的值。本文用真实数据展示"以为一定有两个逆序对"的错误，给出五种语言的实现，并把找逆序对的过程做成分步演示。
完整题目见官方页面（链接在文末）。测试里的树都是"合法二叉搜索树交换了两个结点的值"的结果（题目保证恰好交换了两个）。结果树用层序数组表示。基准解与"找逆序对"完全不同：把所有值排序，再按中序顺序重新写回各个结点。一共 12 组用例，覆盖：官方两个示例、中序里相邻结点被交换（只有一个逆序对）、不相邻的结点被交换（两个逆序对）、交换根和叶子、链状的树：
输入 [[1,3,null,null,2]] 输出 [3,1,null,null,2] 输入 [[3,1,4,null,null,2]] 输出 [2,1,4,null,null,3] 输入 [[1,2,3]] 输出 [2,1,3] 输入 [[2,3,1]] 输出 [2,1,3] 输入 [[3,1,2]] 输出 [2,1,3] 输入 [[4,2,6,7,3,5,1]] 输出 [4,2,6,1,3,5,7]
如果假定一定会出现两个逆序对，只在第二个逆序对处才记录 second，那么被交换的两个结点在中序里相邻时（只有一个逆序对），second 从没被赋值。下面是这种写法与 solve 的真实结果：
# 只在第二个逆序对处记录 second 的写法（相邻结点被交换时只有一个逆序对） [1, 2, 3]: 该写法 -> 崩溃或没有修复：second 是 None solve -> [2, 1, 3] [1, 3, None, None, 2]: 该写法 -> [3, 1, None, None, 2] solve -> [3, 1, None, None, 2] [3, 1, 4, None, None, 2]: 该写法 -> 崩溃或没有修复：second 是 None solve -> [2, 1, 4, None, None, 3] [3, 2, 6, 1, 4, 5, 7]: 该写法 -> 崩溃或没有修复：second 是 None solve -> [4, 2, 6, 1, 3, 5, 7] 随机 20000 棵：该写法出错的有 8574 棵（42.9%）
官方第一个示例 [1, 3, null, null, 2]（中序 3, 2, 1，两个逆序对）两种写法一致；但中序里相邻的结点被交换时，比如 [3, 1, 4, null, null, 2]（官方第二个示例，中序 1, 3, 2, 4，只有一个逆序对 (3, 2)），错误写法里 second 是空，程序崩溃或没有修复。在随机的 20000 棵树里（随机交换其中两个结点，包括相邻的），这种写法出错的有 8574 棵，占 42.9%。正确的写法：每发现一个逆序对，都无条件更新 second；first 只在第一次发现时设置。
做一次迭代的中序遍历，prev 是中序里的上一个结点。每访问一个结点 cur：如果 prev.val > cur.val，说明是一个逆序对：first 如果还是空，就设为 prev（第一个逆序对里较大的那个）；无论是不是第一次，都把 second 设为 cur。遍历结束后交换 first 和 second 的值。因为只是交换值，树的结构不变。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；测试程序把层序数组建成结点对象、调用恢复函数、再把树序列化回数组比较。
Python · 解法代码class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def recover_tree(root): first = second = prev = None # 中序遍历里出现"逆序对"（前一个比后一个大）的位置就是被交换的结点 st, cur = [], root while cur or st: while cur: st.append(cur) cur = cur.left cur = st.pop() if prev and prev.val > cur.val: # 发现一个逆序对 (prev, cur) if first is None: first = prev # 第一个逆序对：较大的那个 prev 就是被换错位置的结点之一 second = cur # 第二个被换错的结点：取「最后一个逆序对」里较小的那个（相邻交换时只有一个逆序对，此时 second 就是这里的 cur） prev = cur cur = cur.right first.val, second.val = second.val, first.val # 只需交换两个结点的值 return root
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,3,null,null,2]] → [3,1,null,null,2] [[3,1,4,null,null,2]] → [2,1,4,null,null,3] [[1,2,3]] → [2,1,3] [[2,3,1]] → [2,1,3] [[3,1,2]] → [2,1,3] [[4,2,6,7,3,5,1]] → [4,2,6,1,3,5,7]
Java · 解法代码class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } } class Solution { public void recoverTree(TreeNode root) { TreeNode first = null, second = null, prev = null; // 中序遍历里出现"逆序对"（前一个比后一个大）的位置就是被交换的结点 Deque<TreeNode> st = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !st.isEmpty()) { while (cur != null) { st.push(cur); cur = cur.left; } cur = st.pop(); if (prev != null && prev.val > cur.val) { // 发现一个逆序对 (prev, cur) if (first == null) first = prev; // 第一个逆序对：较大的那个 prev 就是被换错位置的结点之一 second = cur; // 第二个被换错的结点：取「最后一个逆序对」里较小的那个（相邻交换时只有一个逆序对） } prev = cur; cur = cur.right; } int t = first.val; first.val = second.val; second.val = t; // 只需交换两个结点的值 } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,3,null,null,2]] → [3,1,null,null,2] [[3,1,4,null,null,2]] → [2,1,4,null,null,3] [[1,2,3]] → [2,1,3] [[2,3,1]] → [2,1,3] [[3,1,2]] → [2,1,3] [[4,2,6,7,3,5,1]] → [4,2,6,1,3,5,7]
Go · 解法代码type TreeNode struct { Val int Left, Right *TreeNode } func recoverTree(root *TreeNode) { var first, second, prev *TreeNode // 中序遍历里出现"逆序对"（前一个比后一个大）的位置就是被交换的结点 st := []*TreeNode{} cur := root for cur != nil || len(st) > 0 { for cur != nil { st = append(st, cur) cur = cur.Left } cur = st[len(st)-1] st = st[:len(st)-1] if prev != nil && prev.Val > cur.Val { // 发现一个逆序对 (prev, cur) if first == nil { first = prev // 第一个逆序对：较大的那个 prev 就是被换错位置的结点之一 } second = cur // 第二个被换错的结点：取「最后一个逆序对」里较小的那个（相邻交换时只有一个逆序对） } prev = cur cur = cur.Right } first.Val, second.Val = second.Val, first.Val // 只需交换两个结点的值 }
$ go build -o bin . && ./bin < cases.jsonl [[1,3,null,null,2]] → [3,1,null,null,2] [[3,1,4,null,null,2]] → [2,1,4,null,null,3] [[1,2,3]] → [2,1,3] [[2,3,1]] → [2,1,3] [[3,1,2]] → [2,1,3] [[4,2,6,7,3,5,1]] → [4,2,6,1,3,5,7]
JavaScript · 解法代码class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } } function recoverTree(root) { let first = null, second = null, prev = null; // 中序遍历里出现"逆序对"（前一个比后一个大）的位置就是被交换的结点 const st = []; let cur = root; while (cur || st.length > 0) { while (cur) { st.push(cur); cur = cur.left; } cur = st.pop(); if (prev && prev.val > cur.val) { // 发现一个逆序对 (prev, cur) if (first === null) first = prev; // 第一个逆序对：较大的那个 prev 就是被换错位置的结点之一 second = cur; // 第二个被换错的结点：取「最后一个逆序对」里较小的那个（相邻交换时只有一个逆序对） } prev = cur; cur = cur.right; } [first.val, second.val] = [second.val, first.val]; // 只需交换两个结点的值 }
$ node run.js < cases.jsonl [[1,3,null,null,2]] → [3,1,null,null,2] [[3,1,4,null,null,2]] → [2,1,4,null,null,3] [[1,2,3]] → [2,1,3] [[2,3,1]] → [2,1,3] [[3,1,2]] → [2,1,3] [[4,2,6,7,3,5,1]] → [4,2,6,1,3,5,7]
C++ · 解法代码#include <utility> #include <vector> using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} }; class Solution { public: void recoverTree(TreeNode* root) { TreeNode *first = nullptr, *second = nullptr, *prev = nullptr; // 中序遍历里出现"逆序对"（前一个比后一个大）的位置就是被交换的结点 vector<TreeNode*> st; TreeNode* cur = root; while (cur || !st.empty()) { while (cur) { st.push_back(cur); cur = cur->left; } cur = st.back(); st.pop_back(); if (prev && prev->val > cur->val) { // 发现一个逆序对 (prev, cur) if (!first) first = prev; // 第一个逆序对：较大的那个 prev 就是被换错位置的结点之一 second = cur; // 第二个被换错的结点：取「最后一个逆序对」里较小的那个（相邻交换时只有一个逆序对） } prev = cur; cur = cur->right; } swap(first->val, second->val); // 只需交换两个结点的值 } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,3,null,null,2]] → [3,1,null,null,2] [[3,1,4,null,null,2]] → [2,1,4,null,null,3] [[1,2,3]] → [2,1,3] [[2,3,1]] → [2,1,3] [[3,1,2]] → [2,1,3] [[4,2,6,7,3,5,1]] → [4,2,6,1,3,5,7]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
Python 版本另外和"排序后按中序写回"做了随机对拍：2 到 10 个结点的随机二叉搜索树（值互不相同），随机交换其中两个结点的值（包括中序里相邻的两个）：
随机对拍 20000 组（2 到 10 个结点的随机二叉搜索树（值互不相同，取自 0 到 39），随机交换其中两个结点的值（包括中序里相邻的两个）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。这道题每个结点访问一次，是线性的，额外空间取决于栈（树的高度），Morris 遍历可以降到 O(1)，本文没有实现。
下面的演示用 [3, 1, 4, null, null, 2]。中序遍历依次访问 1、3、2、4：访问 2 时，前一个是 3，3 > 2，是一个逆序对，first = 3、second = 2；后面的 4 没有再产生逆序对。遍历结束交换 3 和 2 的值，得到 [2, 1, 4, null, null, 3]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。