在 2026 年这个算法与硬件深度耦合的时代，当我们再次审视经典的二叉树遍历问题时，会发现传统的教科书解法正面临着前所未有的挑战。今天，我们将深入探讨一种既优雅又极致“硬核”的算法——Morris 遍历。
如果你熟悉传统的二叉树遍历方法，你应该知道，通常我们不是使用递归（利用系统调用栈），就是使用迭代（显式地利用栈数据结构）来实现中序遍历。然而，在今天的开发环境下，随着边缘计算的兴起和嵌入式 AI 模型的普及，每一字节的内存都至关重要。这两种传统方法在空间复杂度上的开销（O(h)）有时会显得捉襟见肘。
今天，我们将向你展示如何实现 Morris 遍历，特别是针对 中序遍历 的场景。这种方法最吸引人的地方在于：它既不需要递归，也不需要栈，就能完成二叉树的遍历。这意味着我们可以将空间复杂度降低到惊人的 O(1)！准备好跟我们一起揭开这个算法的神秘面纱了吗？让我们开始吧。
为什么在 2026 年我们需要 Morris 遍历？不仅仅是 O(1) 空间
在开始编写代码之前，让我们先思考一下为什么我们需要这种算法。在面试中，你会遇到这道题；在生产环境中，你更需要它。
通常，递归方法虽然代码简洁，但它依赖于系统的调用栈。当树的深度非常大（比如退化成链表）时，可能会导致栈溢出，这在处理不可信输入的生产环境中是一个巨大的安全隐患。而迭代法虽然避免了这个问题，但我们需要手动维护一个栈来存储路径，这仍然需要 O(h) 的额外空间。
Morris 遍历的核心思想在于：利用空闲的指针。
在一棵二叉树中，许多节点的右指针其实是空闲的（特别是叶子节点）。Morris 遍历通过临时修改树的结构，利用这些空闲指针来建立“临时链接”，以便在遍历完左子树后能够安全地回溯到根节点。这就像是在森林中留下的路标，指引我们原路返回，而无需额外的背包（栈）。
2026 视角：Agentic AI 与算法选择的博弈
在目前的开发环境下，我们编写代码的方式已经发生了巨大的变化。想象一下，你正在使用 Cursor 或 Windsurf 这样的 AI 原生 IDE。当你输入“二叉树中序遍历”时，AI 通常会第一时间给出递归解法。为什么？因为它最符合人类的直觉，也就是所谓的“Vibe Coding（氛围编程）”。
但是，当我们切换到 Agentic AI（自主智能体） 模式，要求 AI “以最低的内存开销在嵌入式设备上运行”时，优秀的 AI 辅助工具就会意识到栈空间的昂贵，从而推荐 Morris 遍历。
我们的经验是： 理解这种算法不仅是算法能力的体现，更是培养你对“内存敏感性”的关键一课。在面试高频 LeetCode 题目时，这绝对是杀手锏；在开发底层数据库索引（如 B-Tree 遍历）时，这种思路也是无处不在的。
算法核心逻辑：构建与拆除临时链接
让我们通过一个具体的例子来理解这个算法。假设我们正在遍历节点 curr。
#### 1. 情况一：当前节点没有左孩子
这是最简单的情况。既然没有左子树，按照中序遍历（左 -> 根 -> 右）的规则，我们直接处理（打印）当前节点 INLINECODEc699d04b，然后移动到它的右孩子 INLINECODE67b50ab0。
#### 2. 情况二：当前节点有左孩子
这时候，我们需要先去遍历左子树。但问题是，当我们遍历完左子树后，怎么回到 curr 呢？如果没有栈，我们就会迷路。
Morris 遍历的解决办法是：找到当前节点在中序遍历中的前驱节点。
- 什么是前驱节点？ 它是 INLINECODE5f5d1a97 左子树中最右边的那个节点。也就是按照中序遍历，在 INLINECODE77fade11 之前被访问的那个节点。
我们找到这个前驱节点 INLINECODE48c1b7d8 后，会根据 INLINECODEdfcb258d 的右指针状态进行两种操作：
- 操作 A：建立链接
如果 INLINECODE521a2e17 为空（INLINECODEb06302b7），说明这是我们第一次到达这里。我们将 INLINECODE92454cf0 指向 INLINECODEd5605358。这就像是搭了一座桥，让我们未来可以通过 INLINECODEc9f3fdaf 走回 INLINECODEe0d16370。建立好链接后，我们将 INLINECODE8c8698b7 更新为 INLINECODE0c500a28，开始深入左子树。
- 操作 B：拆除链接并处理
如果 INLINECODEc2511a41 不为空，且指向的就是 INLINECODE90bcbc33，这说明我们刚才已经遍历完了左子树，通过这座桥“游”回来了。这时候，我们要做三件事：
1. 拆除桥梁：将 INLINECODEfe5bbef6 重新设为 INLINECODE70c4564b，恢复树的原始结构（这是非常重要的一步，否则树的结构就被破坏了）。
2. 访问节点：处理当前节点 curr。
3. 继续前进：将 INLINECODE3d2f8a63 更新为 INLINECODE7d032787，前往右子树。
代码实战：C++ 现代实现与 AI 辅助注释
理论讲完了，让我们来看看实际的代码。请注意，我们在代码中加入了详细的注释，这在 AI 辅助编程时代尤为重要，它能帮助 AI 更好地理解我们的意图，也能让团队成员快速上手。
#include
#include
using namespace std;
// 定义二叉树节点结构
struct Node {
public:
int data;
Node* left;
Node* right;
// 构造函数
Node(int x) {
data = x;
left = right = nullptr;
}
};
// Morris 中序遍历主函数
vector inOrder(Node* root) {
vector res; // 用于存储遍历结果
Node* curr = root;
while (curr != nullptr) {
// 情况 1：如果没有左孩子
if (curr->left == nullptr) {
// 直接访问当前节点
res.push_back(curr->data);
// 移动到右孩子
curr = curr->right;
}
else {
// 情况 2：如果有左孩子，需要寻找前驱节点
// 前驱节点是左子树中的最右侧节点
Node* prev = curr->left;
// 向右走到尽头，同时要检查是否已经建立了线索
// prev->right != curr 这个检查非常重要，用于判断是否已经遍历过
while (prev->right != nullptr && prev->right != curr) {
prev = prev->right;
}
// 如果前驱的右孩子为空，说明第一次访问
if (prev->right == nullptr) {
// 建立临时链接（线索）
prev->right = curr;
// 继续向左深入
curr = curr->left;
}
else {
// 如果前驱的右孩子指向当前节点，说明左子树已遍历完成
// 恢复树的原始结构（拆除线索）
prev->right = nullptr;
// 访问当前节点（根节点）
res.push_back(curr->data);
// 转向右子树
curr = curr->right;
}
}
}
return res;
}
// 主函数用于测试
int main() {
/* 构建如下的二叉树：
1
/ \
2 3
/ \
4 5
*/
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
// 执行 Morris 遍历
vector result = inOrder(root);
cout << "Morris 中序遍历结果: ";
for (int val : result) {
cout << val << " ";
}
return 0;
}
深入理解与工程化陷阱：生产级代码必备
在我们的实际项目经验中，从算法理论到生产级代码之间，往往隔着一层“陷阱”。让我们来聊聊这些细节。
#### 1. 算法复杂度分析：不仅仅是 O(n)
- 时间复杂度：O(n)。虽然我们在内部循环中寻找前驱节点，看起来像是一个嵌套循环，但实际上，二叉树中的每条边被遍历的次数最多是 3 次（一次建立链接，一次拆除链接，一次正常的移动），所以总的时间复杂度依然是线性的。
- 空间复杂度：O(1)。这是 Morris 遍历最大的亮点。我们只使用了几个指针变量（INLINECODEf18ee94a, INLINECODEca980242），没有使用递归栈或者额外的数据结构。
#### 2. 常见误区与陷阱：那个死循环的噩梦
在实现 Morris 遍历时，有一个非常容易犯错的地方，那就是在寻找前驱节点时的 while 循环条件。
错误的写法：
while (prev->right != nullptr) { // 漏掉了 prev->right != curr 的检查
prev = prev->right;
}
为什么这会导致死循环？
如果你漏掉了 prev->right != curr 的判断，当你第二次回到当前节点时（即已经通过线索返回时），程序会错误地认为前驱节点的右指针还有路可走，从而继续向右跑，导致无限循环。在我们的一次代码审查中，这个 Bug 导致了某个边缘网关服务在处理特定树形结构的数据时直接 CPU 飙升 100%。
正确的做法是： 始终检查 prev->right != curr。这不仅是算法正确的保证，也是 安全左移 理念在算法层面的体现——我们需要在写代码的瞬间就考虑到所有可能的边界情况。
#### 3. 线程安全与并发控制：2026 年的必修课
这是很多传统文章忽略的一点：Morris 遍历会修改树的结构。
这意味着，如果你在一个多线程环境中（比如一个并发的 B+ 树索引），当你在遍历的时候，其他线程试图读取这棵树，可能会读到被“线索化”后的错误状态（前驱节点的右指针指向了祖先节点）。
我们在生产环境中的建议：
- 只读场景：如果树是只读的，Morris 遍历是完美的。
- 读写并发：如果存在并发写或并发读，必须对整棵树加锁，或者使用传统的栈式遍历。虽然栈式遍历空间复杂度高，但它不会破坏数据结构的完整性，这在锁粒度优化上可能更有优势。
实战案例：二叉搜索树的第 K 小元素（LeetCode 230）
让我们来看一个 Morris 遍历大放异彩的 LeetCode 高频题：查找二叉搜索树中第 K 小的元素。
通常我们会用中序遍历把所有节点存入数组，然后取下标。但这需要 O(N) 的空间。如果数据量很大（比如 1 亿个节点），内存直接爆炸。
使用 Morris 遍历，我们可以做到“边遍历、边计数、边放弃”，空间仅用 O(1)。
// C++ 实现：查找 BST 中第 K 小的元素 (Morris 遍历优化版)
int kthSmallest(Node* root, int k) {
Node* curr = root;
int count = 0;
while (curr != nullptr) {
if (curr->left == nullptr) {
// 访问节点
count++;
if (count == k) {
return curr->data; // 找到目标，直接返回
}
curr = curr->right;
} else {
Node* 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;
// 注意：中序遍历的访问点在这里
count++;
if (count == k) {
return curr->data;
}
curr = curr->right;
}
}
}
return -1; // 未找到
}
进阶应用：恢复二叉搜索树（LeetCode 99）
另一个让人惊叹的应用场景是恢复二叉搜索树。当一棵 BST 的两个节点被错误交换后，我们需要找到它们并恢复。传统的做法是用中序遍历存数组，然后找违背排序规律的地方。
但是，有了 Morris 遍历，我们可以在 O(1) 空间内直接找到这两个错误的节点。因为在中序遍历中，我们只需要关注当前节点和前一个节点的值的关系。这正是 Morris 遍历“状态机”特性的优势所在：我们在遍历过程中，能够很容易地保留上一个访问节点的引用（通过 prev 指针或者在拆除链接时记录）。
总结：2026 的算法思维
在这篇文章中，我们从 2026 年的技术视角出发，重新审视了 Morris 遍历。它不仅仅是一个面试算法，更是一种极致利用现有资源的工程哲学。
关键要点回顾：
- 临时链接：利用前驱节点的空闲右指针指向当前节点，作为回溯的路径。
- 状态判断：通过检查
prev->right是否为空，判断我们是第一次到达（建立链接），还是左子树遍历完毕（拆除链接并访问）。 - 结构恢复：访问完左子树后，务必将树的原始结构恢复，即
prev->right = nullptr。 - 工程实践：注意并发安全性，警惕死循环，以及在 AI 辅助编码时代如何写出高性能代码。
随着摩尔定律的放缓，我们不能仅仅依赖硬件性能的提升来掩盖低效的代码。在资源受限的边缘计算、高性能数据库内核开发，甚至是面对 LeetCode 的极限压测用例时，Morris 遍历都展示了“空间换时间”之外的一种思路：通过巧妙的结构重组来达成零空间开销。
希望这篇文章能帮助你彻底理解 Morris 遍历。下次当你遇到“不使用额外空间遍历二叉树”这样的挑战时，你就会知道该如何应对了。试着亲手写一遍代码，或者让 Cursor 帮你生成并优化它，感受一下这种算法的精妙之处吧！