morris后序遍历的核心难点在于无法原生支持「左→右→根」顺序：因线索化仅用right指针，缺乏回溯机制判断右子树是否遍历完毕，故需通过reverse局部链表模拟栈行为，引入两次翻转与复原操作。
Morris后序遍历的核心难点在哪
Morris后序遍历不是前序或中序的简单改写——它必须在不破坏树结构的前提下，逆向输出「左→右→根」顺序，而线索化过程中只能用 right 指针临时连回祖先，无法直接反向访问子树。所以标准 Morris 方法本身不支持真正意义上的零空间后序；常见“Morris后序”实则是用 reverse 局部链表来模拟栈行为，仍属 O(1) 额外空间（不含递归栈），但需两次遍历+翻转。
为什么不能像前序那样直接输出
前序和中序可在找到前驱时立即决定访问时机：前序在首次到达节点时输出，中序在从左子树返回时输出。而后序必须等左右子树都处理完才访问根——而 Morris 无法原生回溯到刚访问完的右子树根，除非你把路径存下来再倒着吐。
- 若强行在断开线索时输出
root，会漏掉右子树未处理的节点 - 若等到右子树完全线索化完成再输出，又缺乏标记机制判断“右子树是否已遍历完毕”
- 因此主流解法是：对每个有左子树的节点，沿其前驱链一路
reverse，收集路径，输出后再reverse复原
关键步骤与易错点
实现时重点不是“怎么连线索”，而是“何时翻转、翻哪段、怎么复原”。整个过程分三步循环：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 当前节点
cur无左子树 → 直接进入右子树（cur = cur->right） - 有左子树 → 找前驱
pre（左子树最右节点），若pre->right == nullptr，建立线索并转向左子树（cur = cur->left） - 若
pre->right == cur，说明左子树已遍历完 → 断开线索，立刻 reverse 从cur->left到pre的链表，逐个输出节点，再 reverse 复原，最后cur = cur->right
容易踩坑的是：reverse 区间起点是 cur->left，终点是 pre（含），且翻转后要记得把最后一个节点的 right 置为 nullptr，否则后续遍历会跳错。
C++ 实现片段（仅核心逻辑）
void morrisPostorder(TreeNode* root) {
TreeNode* dummy = new TreeNode(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;
TreeNode* tail = reverseEdge(cur->left, pre); // 翻转并返回尾节点
printEdge(tail); // 从尾往头输出（即原左→右顺序的逆）
reverseEdge(tail, cur->left); // 复原
cur = cur->right;
}
}
}
delete dummy;
}
reverseEdge 是一个辅助函数，只翻转 from 到 to 的单向链（利用 right 指针），不碰 left；printEdge 从传入节点开始，沿 right 向前打印直到 nullptr。这两个函数必须严格按链表操作写，稍有越界或指针漏置就会导致 segfault 或死循环。
真正零辅助空间的纯 Morris 后序不存在；所谓“O(1) 空间”指的是除若干指针变量外不依赖栈或堆分配——但 reverse 和 printEdge 的局部链表操作，是绕不开的代价。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
