Morris遍历实现O(1)空间的核心是精准复用闲置指针、严格控制访问时机与即时恢复结构;仅用cur、pred、tail、prev四个指针,各司其职、生命周期明确,辅以空指针防护与结构还原。

Morris遍历真正实现O(1)空间,靠的不是“省略变量”,而是**精准复用树中闲置指针 + 严格控制访问时机 + 即时恢复结构**。它不新增节点、不申请栈、不依赖递归调用栈,只用几个固定指针(如cur、pred、tail、prev)完成全部逻辑。关键不在变量数量少,而在每个变量的生命周期、赋值时机和释放动作都经过严密设计。
核心指针的职责与生命周期管理
四个常用指针各司其职,不可混用或提前复位:
-
cur:主游标,始终指向当前处理节点;仅在明确分支内更新(
cur = cur->left或cur = cur->right),绝不写在条件外 -
pred:用于查找左子树最右节点;每次进入
else分支才重新初始化为cur->left,且必须带双条件循环:while (pred->right && pred->right != cur) -
tail 和 prev:仅在后序翻转路径时成对出现;
prev必须初始化为nullptr,否则首节点链断裂;tail终止条件是tail != curr(不是nullptr),避免越界
空指针安全的三重防护机制
所有解引用前必须确保非空,Morris代码崩溃多源于此处疏漏:
- 查
pred前先判cur->left != nullptr,否则跳过整个找前驱逻辑 - 进
while (pred->right && ...)循环时,第一项pred->right保证不空才继续判断第二项 - 翻转路径时,在
tail = curr->left后立即加assert(tail != nullptr)(调试期)或条件跳过(生产期)
访问时机的精确卡点控制
不同遍历顺序的本质差异,全在“何时把cur->val加入结果”这一行的位置:
-
前序:在建立线索前访问——即
pred->right == nullptr分支里,pred->right = cur之前就push_back(cur->val) -
中序:在拆除线索时访问——即
pred->right == cur分支里,pred->right = nullptr之后、cur = cur->right之前 -
后序:不直接访问
cur,而是在pred->right == cur时,沿curr->left → pred路径做链表翻转并逆向输出,最后再整体逆序
结构恢复的不可省略步骤
临时线索只是工具,遍历结束必须还原原始树结构,否则影响后续操作:
- 每次设置
pred->right = cur后,必有对应位置执行pred->right = nullptr - 后序翻转路径中,输出完每个节点后需立即恢复
tail->right = prev(注意不是next) - 所有
nullptr赋值必须显式写出,不能依赖构造函数或初始化列表,避免编译器优化干扰










