恢复二叉搜索树
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你二叉搜索树的根节点 root，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树。
2 <= 节点数 <= 1000，节点值在 32 位有符号整数范围内。
示例 1
示例 2
模拟答题者思考
1. 暴力：收集所有节点值，排序后与当前中序序列比对找两个错位下标，再改值——需要 O(n log n) 且要额外数组，结构明明没变，何必排序？
2. 重复在哪里？BST 的中序遍历一定是严格递增；只交换了两个值，等价于中序数组里恰好有两个位置「破坏了单调性」，形成 1～2 个逆序对 prev > curr。
3. 一次中序 DFS：维护 prev，若 prev.val > node.val，说明这对相邻中序元素逆序——prev 是较大错值、node 是较小错值。
4. 两个逆序对（不相邻交换）：第一次逆序定 first，每次逆序都更新 second，最终 second 是第二次逆序的较小者；只有一个逆序（相邻交换）时，first 与 second 就是这一对。
5. 遍历结束后交换 first.val 与 second.val，不改指针结构，树恢复为合法 BST。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
prev | TreeNode* | 定义：中序遍历中「刚访问完」的上一节点 维护：每访问一个节点后， prev 指向该节点，供下一轮比较更新：处理完 node 后令 prev = node |
first | TreeNode* | 定义：第一次「逆序对」里较大的那个节点（应被换下去的错值） 维护：仅在尚未记录时赋值，之后不再改变 更新：当 prev.val > node.val 且 first 为空时，first = prev |
second | TreeNode* | 定义：当前逆序对里较小的那个节点（应被换上来的错值） 维护：每发现一次逆序都更新为当前的 node（非相邻交换时会出现两次逆序）更新：当 prev.val > node.val 时，second = node |
落码步骤
1. 初始化 prev = first = second = None
2. 定义中序 dfs(node)：空则返回；先 dfs(node.left)
3. 访问根：若 prev 存在且 prev.val > node.val，则若 first 为空令 first = prev，并令 second = node
4. prev = node，再 dfs(node.right)
5. 入口 dfs(root) 后交换 first.val 与 second.val
代码实现
class Solution:
def recoverTree(self, root: TreeNode) -> None:
self.prev = self.first = self.second = None
def dfs(node):
if not node:
return
dfs(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
dfs(node.right)
dfs(root)
if self.first and self.second:
self.first.val, self.second.val = self.second.val, self.first.valclass Solution {
TreeNode* prev = nullptr;
TreeNode* first = nullptr;
TreeNode* second = nullptr;
void dfs(TreeNode* node) {
if (!node) return;
dfs(node->left);
if (prev && prev->val > node->val) {
if (!first) first = prev;
second = node;
}
prev = node;
dfs(node->right);
}
public:
void recoverTree(TreeNode* root) {
dfs(root);
if (first && second)
swap(first->val, second->val);
}
};
// 时间 O(n)，空间 O(h)复杂度分析
O(n)
O(h)（递归栈，h 为树高）
常见坑
相邻两节点交换时只有一次逆序，必须在每次逆序时都更新 second，不能只记录第一次。
比较的是中序相邻的 prev 与当前节点，不是父子比较；前序/后序无法直接看出全局有序性。
误把节点指针交换：题目要求不改变结构，只交换两个节点的 val。
必测边界 Case
root = [1,3,null,null,2] → 交换 1 与 3（中序仅一处逆序）
root = [3,1,4,null,null,2] → first=3, second=2
仅 2 个节点且值颠倒 → 一次逆序即恢复