morris后序遍历的核心约束是零辅助空间且必须确保节点在左右子树均访问完毕后才输出，因此需借助逆序打印技巧：沿左子树构建临时右链、逆序输出并还原指针。
Morris 后序遍历的核心约束是什么？
Morris 遍历要求零辅助空间（即不使用栈、递归调用栈或额外容器），只靠指针重连实现。后序比前序/中序难，关键在于：节点必须在「右子树访问完毕后」才输出，而 Morris 本身是单向遍历，无法回溯。因此必须借助「逆序打印」技巧——在沿左子树向下时，把路径上节点的 right 指针临时反向链接成链表，访问完再还原。
为什么不能直接套用 Morris 中序逻辑？
中序只需在「无左子树时访问当前节点」+「从右子节点回溯时访问根」；后序则必须确保「左、右子树都处理完才访问根」。直接模仿会漏掉右子树未访问就输出根的情况。典型错误现象：std::vector 输出顺序乱序，末尾多出重复节点，或根本没访问到某些叶子。
- 中序 Morris 在找到 predecessor 后，若
predecessor->right == nullptr就访问当前节点并继续右移 - 后序必须等「当前节点的右子树已完整遍历」才访问它，而这只能通过「从右子树最左节点一路向上逆序打印」来模拟
如何安全地构建和还原逆序链？
核心操作是：当从 cur 出发找 predecessor 时，若左子存在，沿 left->right->right... 走到右链末端，把该末端节点的 right 指向 cur，形成临时反向链。之后从该末端开始，沿 right 指针一路向上走，边走边输出（即逆序），最后再把链还原（断开所有临时 right 连接）。
- 每次构建链前，先检查
predecessor->right == cur：若是，说明已访问过左子树，此时应「逆序打印从cur->left到predecessor的整条右链」，然后还原指针 - 打印时用一个临时指针
rev从cur->left开始，逐个翻转链并收集节点值，最后再翻回来（避免破坏结构） - 还原动作不可省略，否则后续遍历会因残留指针导致无限循环或段错误
void morrisPostorder(TreeNode* root) {
TreeNode dummy;
dummy.left = root;
TreeNode* cur = &dummy;
while (cur) {
if (!cur->left) {
cur = cur->right;
} else {
TreeNode* predecessor = cur->left;
while (predecessor->right && predecessor->right != cur) {
predecessor = predecessor->right;
}
if (!predecessor->right) {
predecessor->right = cur;
cur = cur->left;
} else {
predecessor->right = nullptr;
// 逆序打印 cur->left 到 predecessor 的链
reversePrint(cur->left, predecessor);
cur = cur->right;
}
}
}
}
reversePrint 怎么写才不出错？
这个函数负责「从 from 开始，沿 right 指针走到 to，逆序输出中间所有节点」。常见坑是：忘记翻转两次（一次用于遍历，一次用于还原），或边界判断错导致越界访问 nullptr->right。
- 第一步：翻转链 —— 从
from开始，把每个节点的right指向前驱，直到抵达to - 第二步：从
to往回走，挨个输出（此时链已反向，to成了头） - 第三步：再次翻转还原，恢复原始
right关系
真正容易被忽略的是：reversePrint 必须能处理单节点链（from == to），且不能修改 left 指针 —— Morris 后序只动 right，left 始终保持原样。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
