morris前序遍历的核心逻辑是：在第一次抵达某节点时立即访问（而非等待左子树遍历完成），通过临时将左子树最右节点的right指向当前节点建立回溯线索，并在第二次返回时恢复指针；其关键在于访问时机必须前置，否则会导致根节点遗漏或重复访问。
Morris前序遍历的核心逻辑是什么
它不依赖栈或递归，靠临时修改树结构（线索化）实现 O(1) 空间。关键在于：每个左子树的最右节点（前驱）被用来回溯到当前根——即把 pred->right 指向当前节点，完成“打标记”；访问完左子树后，再沿这条临时边返回，恢复原结构。
前序和中序的区别就落在“访问时机”：Morris 前序必须在第一次抵达某节点时立即访问（而非等左子树遍历完），否则会漏掉根节点或重复访问。
为什么不能直接套用中序的 Morris 代码改 print 位置
常见错误是把中序里“进入右子树前访问”的写法挪过来，结果出现重复访问或跳过根节点。比如在 if (pred->right == nullptr) 分支末尾加 cout val，会导致左子树为空的节点被访问两次（一次在打线索时，一次在回溯后）。
正确做法是：
- 当
curr->left == nullptr：直接访问curr，然后跳去curr->right - 当
curr->left != nullptr：先找前驱pred，若pred->right == nullptr，则访问curr，再建立线索pred->right = curr，然后curr = curr->left - 若
pred->right == curr（已访问过左子树）：恢复pred->right = nullptr，curr = curr->right
C++ 实现中容易崩的边界与指针操作
Morris 遍历对空指针极敏感，尤其在找前驱和恢复指针时。典型崩溃点：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 没判
curr->left就直接进 while 找前驱 → 访问空指针 - 前驱
pred找到后，没确认pred->right是空还是已指向curr，就强行赋值 → 破坏线索链 - 恢复
pred->right = nullptr后，忘记把curr移到右子树，导致无限循环 - 节点定义里
right被复用为线索指针，但算法假设原始树的right在无线索时不为curr—— 这要求输入树本身不能含环或非法指针
示例关键片段：
while (curr != nullptr) {
if (curr->left == nullptr) {
result.push_back(curr->val);
curr = curr->right;
} else {
TreeNode* pred = curr->left;
while (pred->right != nullptr && pred->right != curr)
pred = pred->right;
<pre class="brush:php;toolbar:false;"> if (pred->right == nullptr) {
result.push_back(curr->val); // ← 前序：这里访问
pred->right = curr;
curr = curr->left;
} else {
pred->right = nullptr; // ← 必须恢复
curr = curr->right;
}
}}
和递归/栈版本比，Morris 前序有什么隐藏代价
空间是 O(1)，但时间仍是 O(n)，且常数更大：每个边最多被遍历 2 次（一次找前驱，一次恢复）。更关键的是——它**永久修改了原树结构**（哪怕最后恢复），在多线程或只读场景下不可用；如果遍历中途异常退出，树可能处于中间线索态，难以安全恢复。
所以实际项目中，除非明确受限于内存（如嵌入式、超大深度树且禁止栈增长），否则优先选迭代栈版本。Morris 的价值更多在面试考察对指针和树结构的理解深度，而不是日常工程首选。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
