morris后序遍历的核心难点在于访问时机必须滞后于左右子树全部完成，而morris遍历无栈无递归、无法自然回溯，因此不能套用前序/中序逻辑；必须在第二次到达节点时，通过翻转左子树最右路径获取逆后序序列，再整体反转结果，且翻转后须严格恢复指针以保障结构安全。
Morris后序遍历的核心难点在哪
直接套用 Morris 前序/中序的“翻转右子树链”思路会出错——后序要求左→右→根，而 Morris 遍历天然只方便获取“根→左→右”或“左→根→右”的访问流。真正的突破口是：**复用中序 Morris 的结构，但把访问时机从“第一次到达节点”改成“刚完成右子树回溯后”**，这需要额外维护一个“刚访问过的节点”来判断是否该输出当前根。
为什么必须反转右子树链再访问
后序中，某节点的右子树全部处理完后，才轮到它自己。Morris 无法直接跳回父节点，所以得靠临时链表反向遍历从右孩子到当前节点的路径。这个反转不是为了好看，而是为了让 reverseEdge 后能按“右→父”顺序逐个弹出节点，从而逼近后序的“右子树末尾→当前节点”逻辑。
- 不反转就只能从下往上访问（比如从最右叶子往回走），但原链方向是“父→右→右…”，没法自然倒推
-
reverseEdge函数必须原地修改指针，不能用栈或额外空间 - 反转后记得再反转回去，否则破坏树结构（尤其多次遍历时）
关键代码段怎么写才不出错
核心在于三处易错点：空右子树时的访问时机、反转链表的边界处理、以及恢复指针的条件判断。下面是最简可行骨架（C++11+）：
void morrisPostorder(TreeNode* root) {
TreeNode dummy(0);
dummy.left = root;
TreeNode* cur = &dummy;
while (cur) {
if (!cur->left) {
cur = cur->right;
} else {
TreeNode* pred = cur->left;
while (pred->right && pred->right != cur) pred = pred->right;
if (!pred->right) {
pred->right = cur;
cur = cur->left;
} else {
pred->right = nullptr;
reverseEdge(cur->left, pred); // 反转从cur->left到pred的链
TreeNode* tail = pred;
while (tail) {
cout val right;
}
reverseEdge(pred, cur->left); // 恢复
cur = cur->right;
}
}
}
}
<p>void reverseEdge(TreeNode<em> from, TreeNode</em> to) {
TreeNode<em> prev = nullptr, </em>next;
while (from != to) {
next = from->right;
from->right = prev;
prev = from;
from = next;
}
// 注意：to 节点的 right 不动，它是链尾
}</p>
注意：reverseEdge 的终止条件是 from != to，不是 from 为空；to 是反转区间的终点（含），但它的 right 字段不参与反转——这是很多实现漏掉的细节。
和递归/栈版本比有什么代价
Morris 后序省了 O(h) 栈空间，但时间上多了一次链表反转（均摊仍 O(n)）。真正麻烦的是调试：指针改来改去容易野指针，尤其 pred->right = nullptr 和 reverseEdge 的配合稍有偏差就会无限循环或访问非法地址。
- 务必在每次
reverseEdge前后加断言，检查pred是否真指向cur->left的最右节点 - 测试用例至少包含：单节点、只有左子树、只有右子树、满二叉树、带空子节点的不平衡树
- 别试图在
reverseEdge里做输出——先存到 vector 再输出更安全，避免边反转边访问引发指针混乱
实际项目里，除非内存极度受限且树高极大，否则直接用栈模拟后序更可靠。Morris 后序本质是“用两次反转换空间”，理解它怎么绕过栈比硬背代码更重要。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
