前言LeetCode 第 99 题「恢复二叉搜索树」的描述是一棵二叉搜索树的其中两个节点被错误地交换了在不改变树结构的前提下恢复这棵树。题目通常要求给出原地算法进阶要求使用 O(1) 额外空间。解题的钥匙是中序遍历。二叉搜索树的中序序列严格递增两个节点被交换后序列中会出现一处或两处「前一个值大于后一个值」的逆序。如果被交换的两个节点在中序序列里相邻只有一处逆序这一对就是答案如果它们不相邻会出现两处逆序第一处的前一个节点和第二处的后一个节点才是被交换的两个节点。常见错误有三个。第一只记录第一处逆序的两个节点遇到不相邻的情况会交换错。第二每遇到逆序就覆盖first导致最终记录的是最后一处逆序的前一个节点。第三用 Morris 遍历时忘记拆除临时线索遍历结束后树的结构被破坏。本文给出两种实现基于数组的直观版本以及满足进阶要求的 Morris 中序遍历。示例以 C17 为准节点值按题目常见设定视为互不相同。一、从逆序对定位两个节点设中序序列为a[0..n-1]。正常情况它严格递增。交换两个位置i j的元素后若j i 1只在a[i]与a[i1]之间出现一次下降逆序对是(a[i], a[i1])。若j i 1则在i处出现一次下降a[i] a[i1]在j-1处再出现一次下降a[j-1] a[j]。被交换的两个值是第一处下降的前者和第二处下降的后者。因此扫描时维护两个指针第一次遇到下降把前一个节点记为first此后每次遇到下降都把当前节点记为second。循环结束时交换first和second的值。情况逆序出现次数firstsecond被交换节点相邻1第一处下降的前者第一处下降的后者被交换节点不相邻2第一处下降的前者第二处下降的后者这个规则对两种情况都成立所以代码里不需要分类讨论。二、直观解法收集中序节点最直接的写法是递归中序遍历把所有节点指针按顺序放进std::vector再线性扫描找出两个节点交换它们的值。时间复杂度 O(n)空间复杂度 O(n)。// 适用于 C17#include algorithm#include vectorstruct 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::vectorTreeNode* 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::vectorTreeNode* 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 遍历利用叶子节点的空右指针临时把当前节点的中序前驱与当前节点连起来从而在不用栈、不用递归的情况下完成中序遍历。核心规则是当前节点cur没有左孩子访问cur然后cur cur-right。当前节点有左孩子找到左子树的最右节点pred中序前驱。若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) 空间解法。// 适用于 C17class 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循环会沿着线索继续走可能陷入死循环或访问到不该访问的节点。四、完整示例// 适用于 C17#include algorithm#include iostreamstruct 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 1TreeNode* 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 3cur移到 2。2 有左孩子吗示例里没有访问 2prev从空变成 2cur沿右指针回到 3。3 再次有左孩子前驱 2 的右指针等于 3说明左子树遍历完拆除线索访问 3。此时prev是 22 3不成立不记录。cur移到 11 没有左孩子访问 1prev是 33 1成立first 3second 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 遍历。坑点七交换节点值后忘记验证。❌ 认为只要找到两个节点就必然正确没有用中序复检。✅ 恢复后再次中序遍历确认序列严格递增。坑点八忽略重复值的前提。❌ 树中有重复值时仍按判断逆序可能漏判或误判。✅ 明确题目保证值互异否则改用能区分节点身份的比较方式。总结方案时间复杂度空间复杂度适用递归中序 数组O(n)O(n)直观、易写面试先给显式栈迭代中序O(n)O(h)避免递归栈溢出Morris 中序O(n)O(1)满足进阶要求本题的难点不在遍历而在「两处逆序如何对应到两个节点」这一层映射。把中序序列写出来手动交换一次相邻节点、一次不相邻节点观察下降出现的位置规则就很清楚了。Morris 遍历则是把这份观察落到 O(1) 空间的标准技巧写完后务必检查线索是否全部拆除。