C++实现LeetCode(99.复原二叉搜索树)

前言

LeetCode 第 99 题「恢复二叉搜索树」的描述是：一棵二叉搜索树的其中两个节点被错误地交换了，在不改变树结构的前提下恢复这棵树。题目通常要求给出原地算法，进阶要求使用 O(1) 额外空间。

解题的钥匙是中序遍历。二叉搜索树的中序序列严格递增，两个节点被交换后，序列中会出现一处或两处「前一个值大于后一个值」的逆序。如果被交换的两个节点在中序序列里相邻，只有一处逆序，这一对就是答案；如果它们不相邻，会出现两处逆序，第一处的前一个节点和第二处的后一个节点才是被交换的两个节点。

常见错误有三个。第一，只记录第一处逆序的两个节点，遇到不相邻的情况会交换错。第二，每遇到逆序就覆盖first，导致最终记录的是最后一处逆序的前一个节点。第三，用 Morris 遍历时忘记拆除临时线索，遍历结束后树的结构被破坏。

本文给出两种实现：基于数组的直观版本，以及满足进阶要求的 Morris 中序遍历。示例以 C++17 为准，节点值按题目常见设定视为互不相同。

一、从逆序对定位两个节点

设中序序列为a[0..n-1]。正常情况它严格递增。交换两个位置i < j的元素后：

• 
  
• 若j == i + 1，只在a[i]与a[i+1]之间出现一次下降，逆序对是(a[i], a[i+1])。
• 
  
• 若j > i + 1，则在i处出现一次下降a[i] > a[i+1]，在j-1处再出现一次下降a[j-1] > a[j]。被交换的两个值是第一处下降的前者和第二处下降的后者。
• 
  

因此扫描时维护两个指针：第一次遇到下降，把前一个节点记为first；此后每次遇到下降，都把当前节点记为second。循环结束时交换first和second的值。

这个规则对两种情况都成立，所以代码里不需要分类讨论。

二、直观解法：收集中序节点

最直接的写法是递归中序遍历，把所有节点指针按顺序放进std::vector，再线性扫描找出两个节点，交换它们的值。时间复杂度 O(n)，空间复杂度 O(n)。

// 适用于 C++17
#include <algorithm>
#include <vector>

struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class SolutionVector {
public:
void recoverTree(TreeNode* root) {
std::vector<TreeNode*> nodes;
inorder(root, nodes);

TreeNode* first = nullptr;
TreeNode* second = nullptr;
for (std::size_t i = 1; i < nodes.size(); ++i) {
if (nodes[i - 1]->val > nodes[i]->val) {
if (first == nullptr) {
first = nodes[i - 1];
}
second = nodes[i];
}
}
if (first != nullptr && second != nullptr) {
std::swap(first->val, second->val);
}
}

private:
void inorder(TreeNode* node, std::vector<TreeNode*>& out) {
if (node == nullptr) return;
inorder(node->left, out);
out.push_back(node);
inorder(node->right, out);
}
};

second = nodes[i]没有放在if (first == nullptr)里面，这是关键。相邻交换时只有一次下降，first和second在同一次迭代中被赋值；不相邻时，第一次下降确定first，第二次下降把second更新为正确的节点。如果只在第一次下降时同时给两者赋值，不相邻的情况就会交换错。

递归版本在树很深时可能栈溢出，而且额外数组不满足 O(1) 空间的进阶要求。实际面试中，写完这一版通常会被追问如何优化空间。

三、Morris 中序遍历：O(1) 空间

Morris 遍历利用叶子节点的空右指针，临时把当前节点的中序前驱与当前节点连起来，从而在不用栈、不用递归的情况下完成中序遍历。核心规则是：

1. 
   
2. 当前节点cur没有左孩子：访问cur，然后cur = cur->right。
3. 
   
4. 当前节点有左孩子：找到左子树的最右节点pred（中序前驱）。
5. 
   

• 
  
• 若pred->right == nullptr，说明是第一次到达，建立线索pred->right = cur，然后cur = cur->left。
• 
  
• 若pred->right == cur，说明左子树已经遍历完，拆除线索pred->right = nullptr，访问cur，然后cur = cur->right。
• 
  

每个节点被访问两次（有左孩子时），每次找前驱的路径总长度是 O(n)，整体时间复杂度仍是 O(n)，额外空间只有几个指针。

把「访问」替换成「比较前驱值与当前值、更新first和second」，就得到本题的 O(1) 空间解法。

// 适用于 C++17
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode* first = nullptr;
TreeNode* second = nullptr;
TreeNode* prev = nullptr;
TreeNode* cur = root;

while (cur != nullptr) {
if (cur->left == nullptr) {
visit(cur, prev, first, second);
cur = cur->right;
} else {
TreeNode* pred = cur->left;
while (pred->right != nullptr && pred->right != cur) {
pred = pred->right;
}

if (pred->right == nullptr) {
pred->right = cur;
cur = cur->left;
} else {
pred->right = nullptr;
visit(cur, prev, first, second);
cur = cur->right;
}
}
}

if (first != nullptr && second != nullptr) {
std::swap(first->val, second->val);
}
}

private:
static void visit(TreeNode* node, TreeNode*& prev,
TreeNode*& first, TreeNode*& second) {
if (prev != nullptr && prev->val > node->val) {
if (first == nullptr) {
first = prev;
}
second = node;
}
prev = node;
}
};

visit的参数prev、first、second都是引用，因为要在函数内部修改调用方的指针。写成按值传递，修改只作用于副本，外面永远是空指针。

前驱查找的循环条件必须同时检查pred->right != nullptr和pred->right != cur。只写前者，第二次到达时线索已经指向cur，循环会沿着线索继续走，可能陷入死循环或访问到不该访问的节点。

四、完整示例

// 适用于 C++17
#include <algorithm>
#include <iostream>

struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode* first = nullptr;
TreeNode* second = nullptr;
TreeNode* prev = nullptr;
TreeNode* cur = root;

while (cur != nullptr) {
if (cur->left == nullptr) {
visit(cur, prev, first, second);
cur = cur->right;
} else {
TreeNode* pred = cur->left;
while (pred->right != nullptr && pred->right != cur) {
pred = pred->right;
}
if (pred->right == nullptr) {
pred->right = cur;
cur = cur->left;
} else {
pred->right = nullptr;
visit(cur, prev, first, second);
cur = cur->right;
}
}
}

if (first != nullptr && second != nullptr) {
std::swap(first->val, second->val);
}
}

private:
static void visit(TreeNode* node, TreeNode*& prev,
TreeNode*& first, TreeNode*& second) {
if (prev != nullptr && prev->val > node->val) {
if (first == nullptr) first = prev;
second = node;
}
prev = node;
}
};

void printInorder(const TreeNode* node) {
if (node == nullptr) return;
printInorder(node->left);
std::cout << node->val << ' ';
printInorder(node->right);
}

int main() {
// 构造 3 2 1 这棵树的中序应为 1 2 3，
// 现在 1 和 3 被交换，中序是 3 2 1
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(2);
root->right = new TreeNode(1);

Solution solution;
solution.recoverTree(root);

printInorder(root);
std::cout << '\n';

delete root->left;
delete root->right;
delete root;
return 0;
}

推演 Morris 过程。cur指向 3，有左孩子 2。找前驱：2 的右孩子为空，建立线索2->right = 3，cur移到 2。2 有左孩子吗？示例里没有，访问 2，prev从空变成 2，cur沿右指针回到 3。3 再次有左孩子，前驱 2 的右指针等于 3，说明左子树遍历完，拆除线索，访问 3。此时prev是 2，2 > 3不成立，不记录。cur移到 1，1 没有左孩子，访问 1；prev是 3，3 > 1成立，first = 3，second = 1。遍历结束，交换 3 和 1 的值。中序输出为 1 2 3。

注意示例只触发了相邻交换的情况。要测试不相邻的情况，可以构造中序为 1 5 3 4 2 的树（交换 5 和 2），此时扫描会在 5 与 3 之间记录first = 5，在 4 与 2 之间把second更新为 2，最终交换 5 和 2。把这段序列按二叉搜索树插入建树后交给recoverTree，可以验证第二种分支。

五、换值还是换节点

题目要求「不改变树结构」，最常见的做法是交换两个节点的值，本文的代码也是这样。如果节点值不允许修改（例如值是只读的），就必须调整节点的连接关系，把两个节点在树中的位置互换，这需要记录父节点并处理四种连接组合，代码量明显增加。面试时应先确认题目允许交换值，多数版本的 LeetCode 99 都是允许的。

另外，题目保证恰好有一对节点被交换。如果输入不满足这个前提，或者树中存在重复值，基于「严格递增」的判断会失效：重复值交换后中序序列可能看不出变化。工程代码应当先校验输入，或者明确文档中的前置条件。

常见坑点

坑点一：只记录第一处逆序。

❌ 遇到第一处下降就把first和second都定下来，不相邻交换时找错节点。

✅ 第一次下降只定first，之后每次下降都更新second。

坑点二：每次下降都覆盖first。

❌first = prev; second = node;写在循环体里不加判断，最终记录的是最后一处逆序。

✅first只在第一次下降时赋值。

坑点三：Morris 遍历后不拆除线索。

❌ 只建立pred->right = cur，恢复时不置回nullptr，树中留下环。

✅ 第二次到达时先pred->right = nullptr;再访问当前节点。

坑点四：前驱查找条件写错。

❌while (pred->right != nullptr) pred = pred->right;，遇到已建立的线索会走过头。

✅ 条件写成pred->right != nullptr && pred->right != cur。

坑点五：visit参数按值传递。

❌void visit(TreeNode* node, TreeNode* prev, TreeNode* first, TreeNode* second)，外部指针永远不更新。

✅ 需要修改的指针用引用传递。

坑点六：递归中序处理超深树。

❌ 链状树递归深度达到 n，栈溢出。

✅ 用显式栈的迭代中序或 Morris 遍历。

坑点七：交换节点值后忘记验证。

❌ 认为只要找到两个节点就必然正确，没有用中序复检。

✅ 恢复后再次中序遍历，确认序列严格递增。

坑点八：忽略重复值的前提。

❌ 树中有重复值时仍按>判断逆序，可能漏判或误判。

✅ 明确题目保证值互异；否则改用能区分节点身份的比较方式。

总结

本题的难点不在遍历，而在「两处逆序如何对应到两个节点」这一层映射。把中序序列写出来，手动交换一次相邻节点、一次不相邻节点，观察下降出现的位置，规则就很清楚了。Morris 遍历则是把这份观察落到 O(1) 空间的标准技巧，写完后务必检查线索是否全部拆除。