morris后序遍历的核心约束是根节点必须在左右子树均访问完毕后才处理，因此无法边线索化边输出，必须在第二次抵达节点时逆序打印其左子树的右边界，并在全局结果上再执行一次reverse以获得正确“左→右→根”顺序。
Morris后序遍历的核心约束是什么？
Morris后序不能像前序、中序那样直接“边找边输出”，因为根节点必须在左右子树都访问完之后才处理。这意味着你无法靠单次线索化就完成输出——必须在第二次经过某个节点时，逆序打印其左子树的右边界（即从该节点的左孩子开始，沿右指针一路走到尽头，再倒着输出这条链）。
这个“逆序右边界”是 Morris 后序唯一可依赖的局部结构，也是所有实现绕不开的支点。一旦忽略这点，要么漏节点，要么重复输出。
如何安全反转右边界并避免破坏线索？
反转操作必须在不干扰 Morris 线索的前提下进行，关键在于：只对当前节点左子树中、尚未被线索化过的右链做临时反转，并在打印后立即还原。
实操要点：
- 当
cur->left存在，且pre = cur->left的最右节点指向cur（即已建立线索），说明这是第二次到达cur；此时进入右边界处理 - 用临时指针
node从cur->left出发，沿right指针走到尽头，再原地反转该链（类似链表反转），但只改right字段，不动left - 反转完成后，从链尾（即原左子树的最右节点）开始逐个输出，直到回到
cur->left - 输出完毕后，**必须再反转一次**，恢复原始
right指针方向，否则后续线索会失效
// 示例：反转右边界并打印（伪代码逻辑）
TreeNode* reverse_right_edge(TreeNode* head) {
TreeNode* prev = nullptr;
while (head) {
TreeNode* next = head->right;
head->right = prev;
prev = head;
head = next;
}
return prev; // 返回新头（原尾）
}
为什么不能复用 Morris 中序的线索逻辑？
Morris 中序靠“第一次到某节点时建立线索，第二次到时输出”，天然满足顺序要求；而后序需要把左子树的右边界作为一块独立数据块来处理，而这个边界在中序线索化过程中已被反复修改过（比如某节点的 right 可能曾指向祖先，也可能被临时设为 nullptr）。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
典型陷阱：
- 误以为只要检测
pre->right == cur就能直接输出cur→ 实际此时左子树还没“完整暴露”，右边界可能断裂 - 在反转时不检查
right是否原本就是nullptr或指向真实右孩子 → 导致还原失败或访问野指针 - 忘记在最后补上一次 root 的右边界处理（若 root 有左子树）→ 漏掉整棵左子树的后序序列
边界 case 如何验证？
最易出错的是空树、单节点、只有左子树、只有右子树、完全不平衡树（如全左斜树）。重点验证：
关键检查点：
-
root == nullptr→ 不进主循环，直接返回空结果 -
root->left == nullptr && root->right == nullptr→ 应仅输出root一次 -
root->left != nullptr && root->right == nullptr→ 必须触发左子树右边界反转逻辑，且最终输出顺序为 “左子树后序 + root” - 任意节点的
right在函数退出后必须与输入一致（可通过手动画三节点树走一遍指针变化确认）
Morris 后序真正的复杂点不在流程设计，而在每次反转/还原时对 right 字段的精确控制——少一次赋值，或多一次解引用，都会让线索断裂或内存越界。写完务必用纸笔模拟一个 4 节点左斜树，把每个 right 的变化步骤标出来。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
