Morris 中序遍历 (O(1) 空间二叉树遍历)¶
在二叉树遍历算法中，递归方法与基于显式栈（std::stack）的迭代方法是最常见的解法。这两种方法的空间复杂度均为 \(O(h)\)（\(h\) 为树的高度，最坏情况下当树退化为链表时为 \(O(n)\)）。
1979 年，J. H. Morris 提出了著名的 Morris 遍历算法（Morris Traversal）。该算法能够在时间复杂度为 \(O(n)\) 的前提下，实现严格的 \(O(1)\) 额外空间复杂度（不使用递归调用栈，也不借助任何外部数据结构）。
1. 核心思想与空间优化直觉¶
1.1 为什么传统遍历需要栈空间？¶
在二叉树中，节点的指针是指向子节点的单向指针： - 当遍历深入到左子树后，如果没有栈或父指针（Parent Pointer），程序无法在遍历完左子树后返回当前根节点； - 递归调用的函数调用栈，或者迭代写法中的显式栈，本质上就是为了记住“回头路”。
1.2 Morris 的破局点：闲置空指针与线索化 (Threading)¶
在一棵包含 \(n\) 个节点的二叉树中，每个节点有 2 个子指针，总计 \(2n\) 个指针。其中只有 \(n - 1\) 个指针指向了有效的子节点，剩下多达 \(n + 1\) 个指针全部是闲置的 nullptr！
Morris 算法的核心直觉是：
利用叶子节点大量闲置的右指针（
nullptr），临时指向当前节点作为“回程车道（线索）”；当左子树遍历完毕顺着线索返回后，再将该指针重新恢复为nullptr，还原树的原貌。
graph TD
subgraph "传统二叉树 (叶子节点右指针为空)"
A1((2)) --> B1((1))
A1 --> C1((3))
B1 -.->|"right 为 nullptr (闲置)"| Null1[nullptr]
end
subgraph "Morris 临时线索化 (利用闲置指针回溯)"
A2((2)) --> B2((1))
A2 --> C2((3))
B2 -.->|临时线索: 指向中序后继| A2
end2. Morris 中序遍历的算法步骤¶
设当前遍历指针为 curr：
graph TD
Start([开始: curr 指向根节点]) --> CheckNull{curr 是否为空?}
CheckNull -->|是| End([遍历结束])
CheckNull -->|否| CheckLeft{curr->left 是否为空?}
CheckLeft -->|为空| Visit1[1. 访问 curr 节点]
Visit1 --> MoveRight1[2. curr = curr->right]
MoveRight1 --> CheckNull
CheckLeft -->|不为空| FindPred[寻找 curr 在左子树的中序前驱 predecessor]
FindPred --> CheckPredRight{predecessor->right 状态?}
CheckPredRight -->|等于 nullptr: 首次到达| BuildThread[建立线索: predecessor->right = curr]
BuildThread --> MoveLeft[curr = curr->left]
MoveLeft --> CheckNull
CheckPredRight -->|等于 curr: 二次返回| RemoveThread[拆除线索: predecessor->right = nullptr]
RemoveThread --> Visit2[访问 curr 节点]
Visit2 --> MoveRight2[curr = curr->right]
MoveRight2 --> CheckNull详细分步逻辑：¶
- 若
curr->left == nullptr： - 说明当前节点没有左子树，按照中序遍历规则（左 \(\to\) 根 \(\to\) 右），当前节点就是接下来要访问的节点；
- 访问
curr（输出或存入结果数组）； -
移动到右子树：
curr = curr->right。 -
若
curr->left != nullptr： - 找到
curr在左子树中的中序前驱节点（Predecessor）：即curr->left的最右侧节点（沿着右子树一直走到尽头，但不能是curr本身）； - 分支 A（首次到达
curr）：若predecessor->right == nullptr- 说明左子树尚未遍历；
- 建立临时线索：
predecessor->right = curr； - 指针向左推进：
curr = curr->left。
- 分支 B（二次返回
curr）：若predecessor->right == curr- 说明左子树已经全部遍历完毕，且当前是通过之前建立的线索“回溯”到了
curr； - 拆除线索，恢复原树结构：
predecessor->right = nullptr； - 访问
curr（按照左 \(\to\) 根 \(\to\) 右，此时左子树已完结，访问根节点）； - 指针向右推进：
curr = curr->right。
- 说明左子树已经全部遍历完毕，且当前是通过之前建立的线索“回溯”到了
3. 复杂度深度证明¶
3.1 空间复杂度：严格 O(1)¶
- 整个算法自始至终只使用了两个指针变量：
curr（当前遍历指针）和prev（寻找前驱节点的辅助指针）； - 没有使用任何递归调用栈，也没有使用
vector、stack等辅助数据结构； - 额外空间复杂度严格为 \(O(1)\)。
3.2 时间复杂度：严格 O(n)¶
初学者常有疑问：在外层 while (curr) 循环中，每次遇到左子树都会执行一个内层 while (prev->right && prev->right != curr) 寻找前驱节点，这会不会导致时间复杂度退化为 \(O(n^2)\)？
答案是：不会，时间复杂度为严格的 \(O(n)\)。
摊还分析证明：¶
- 对于二叉树中的任意一条边，在整个 Morris 遍历过程中最多只会被经过 3 次：
- 第一次经过：在
curr处寻找前驱节点，自顶向下遍历该边，用于建立线索； - 第二次经过：正常遍历左子树时向下移动指针；
- 第三次经过：再次寻找前驱节点以检测并拆除线索。
- 一棵包含 \(n\) 个节点的树恰好有 \(n - 1\) 条边。所有边被访问的次数总和不超过 \(3(n - 1) = 3n - 3\) 次；
- 因此，总时间复杂度为严格的 \(O(n)\)。
4. 标准 C++ 代码实现¶
4.1 Morris 中序遍历标准模板¶
#include <vector>
#include <iostream>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
std::vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> result;
TreeNode* curr = root;
while (curr != nullptr) {
if (curr->left == nullptr) {
// 1. 没有左子树，直接访问当前节点并转向右子树
result.push_back(curr->val);
curr = curr->right;
} else {
// 2. 有左子树，寻找当前节点在中序遍历下的前驱节点
TreeNode* prev = curr->left;
while (prev->right != nullptr && prev->right != curr) {
prev = prev->right;
}
if (prev->right == nullptr) {
// 首次访问：建立从前驱指向当前节点的临时线索
prev->right = curr;
curr = curr->left;
} else {
// 二次访问：左子树已遍历完成，拆除线索并访问当前节点
prev->right = nullptr;
result.push_back(curr->val);
curr = curr->right;
}
}
}
return result;
}
};
4.2 前序遍历与中序遍历的唯一区别¶
Morris 算法同样可以用于前序遍历（Preorder Traversal：根 \(\to\) 左 \(\to\) 右）。 二者的代码结构 95% 完全相同，唯一的差异仅仅是“访问节点的时机”：
- 中序遍历：在拆除线索时（二次到达
curr时）访问curr； - 前序遍历：在建立线索时（首次到达
curr时）访问curr！
// Morris 前序遍历的核心差异对比：
if (prev->right == nullptr) {
result.push_back(curr->val); // [前序] 首次到达即访问
prev->right = curr;
curr = curr->left;
} else {
prev->right = nullptr; // 拆除线索
// [中序] 此处原本是 result.push_back(curr->val);
curr = curr->right;
}
5. 经典面试实战应用¶
5.1 恢复二叉搜索树 (LeetCode 99 - 经典必考)¶
题目描述：二叉搜索树（BST）中的两个节点被错误地交换了位置。请在不改变其结构的前提下恢复这棵树。 进阶要求：使用 \(O(1)\) 的空间复杂度完成。
解题思路：¶
BST 的中序遍历序列应该是严格单调递增的。如果交换了两个节点，中序遍历中会出现逆序对（\(prev.val > curr.val\)）： - 若两个错误节点不相邻：会出现两次逆序对。第一个错误节点是第一个逆序对中较大的数，第二个错误节点是第二个逆序对中较小的数； - 若两个错误节点相邻：只会出现一次逆序对。 - 结合 Morris 中序遍历，在遍历过程中维护前驱节点值，即可在 \(O(1)\) 额外空间 下完美解出本题！
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *first = nullptr, *second = nullptr;
TreeNode *last = nullptr; // 记录中序遍历上一个被访问的节点
TreeNode *curr = root;
while (curr != nullptr) {
if (curr->left == nullptr) {
// 处理当前节点逻辑
if (last && last->val > curr->val) {
if (!first) first = last;
second = curr;
}
last = curr;
curr = curr->right;
} else {
TreeNode* prev = curr->left;
while (prev->right && prev->right != curr) {
prev = prev->right;
}
if (prev->right == nullptr) {
prev->right = curr;
curr = curr->left;
} else {
prev->right = nullptr;
// 处理当前节点逻辑
if (last && last->val > curr->val) {
if (!first) first = last;
second = curr;
}
last = curr;
curr = curr->right;
}
}
}
if (first && second) {
std::swap(first->val, second->val);
}
}
};
5.2 二叉搜索树中的众数 (LeetCode 501)¶
在 BST 中寻找出现频率最高的众数，常规解法是用哈希表统计频次（\(O(n)\) 空间）。利用 Morris 中序遍历生成的有序序列，相同的数必定连续出现，只需统计当前数字的连续频次并与最大频次比对，就能在 \(O(1)\) 额外空间 内完成统计。
6. 优缺点与工程避坑指南¶
6.1 优点¶
- 极限空间优化：无栈空间开销，对内存极度敏感的嵌入式系统极为友好；
- 彻底防御爆栈：即使面对深度高达数十万的极端倾斜树，也不会发生函数调用栈溢出（Stack Overflow）。
6.2 缺点与工业界避坑¶
- 破坏树结构与非线程安全：
- 遍历过程中会动态修改节点的
right指针，如果多个线程并发只读访问该二叉树，会导致不可预测的严重并发冲突； - 异常安全性差：
- 若遍历过程中抛出未捕获的异常，或者通过
break/return提前退出且未清理线索，二叉树中将残留环形结构，导致后续遍历陷入死循环并引发内存泄漏。