morris后序遍历更难写是因为其需翻转右子路径并双重访问：先翻转链表模拟栈，反向输出后再恢复指针；关键判断是pre->right == cur的线索闭环，而非仅检查cur->right是否为空。
为什么Morris后序遍历比前序/中序更难写
Morris遍历的核心是用叶子节点的right指针临时指向其前驱（inorder predecessor），但后序要求“左右根”，而线索化过程天然按“根→左→右”推进，无法直接拿到左右子树访问完成的信号。所以必须靠**翻转链表+两次访问**来模拟：第一次沿右链向下时翻转，第二次原路返回时输出——这步翻转和恢复是关键，漏掉就导致指针错乱或死循环。
核心步骤：翻转右子路径 + 双重访问控制
当从某节点cur出发向左子树探查后返回，若发现cur->right非空且未被线索化，说明它有右子树；此时需沿着cur->right → right->right → ...走到最左节点，再一路翻转该单向链表（即把每个节点的right指向前一个），最后从尾部反向遍历并输出——等同于把右子树的“右-右-右...”路径当作一个临时栈。
- 每次翻转前先保存原始
right头节点（记为tail），翻转完从tail开始遍历输出 - 翻转结束后必须再走一遍链表，把
right指针恢复原状，否则破坏树结构 - 只有当
cur的右子树已被线索化（即cur->right指向cur本身）时，才真正输出cur值
关键判断：如何识别“右子树已处理完毕”
Morris后序不依赖标记位或栈，而是靠线索指针是否构成环：if (pre->right == cur) 表示pre是cur的前驱，且cur的右链已被用来回溯——此时cur的左右子树都已访问完，可以安全输出。
- 错误写法：
if (!cur->right)—— 这只说明无右子树，不代表右子树已处理 - 正确依据：必须检测
pre->right == cur这个线索闭环，它是Morris后序唯一的“完成信号” - 注意
pre是在找前驱过程中动态更新的，不是固定父节点
完整骨架代码（C++，无递归无栈）
void morrisPostorder(TreeNode* root) {
TreeNode dummy(0);
dummy.left = root;
TreeNode* cur = &dummy;
while (cur) {
if (!cur->left) {
cur = cur->right;
} else {
TreeNode* pre = cur->left;
while (pre->right && pre->right != cur) pre = pre->right;
if (!pre->right) {
pre->right = cur;
cur = cur->left;
} else {
pre->right = nullptr;
// 翻转 cur->left 的右链并输出
TreeNode* tail = reverseRightChain(cur->left);
printFromTail(tail);
reverseRightChain(tail); // 恢复
cur = cur->right;
}
}
}
}
<p>TreeNode<em> reverseRightChain(TreeNode</em> head) {
TreeNode<em> prev = nullptr, </em>curr = head;
while (curr) {
TreeNode* next = curr->right;
curr->right = prev;
prev = curr;
curr = next;
}
return prev; // 返回新头（原尾）
}</p><p>void printFromTail(TreeNode* tail) {
while (tail) {
cout val right;
}
}</p>
真正容易崩的地方不在逻辑分支，而在reverseRightChain的边界：如果head为空或单节点，翻转函数必须不崩溃；且printFromTail不能假设链表一定有环——它只处理已翻转的单向链。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
