Morris后序遍历必须翻转子路径,因其需实现“左→右→根”顺序而仅能线性推进,故先按“根→右→左”遍历再翻转输出;翻转时prev必须显式初始化为nullptr,且恢复指针须在输出前立即执行,否则导致链表错乱或崩溃。

为什么 Morris 后序遍历必须翻转子路径
因为后序要求“左→右→根”,而 Morris 遍历本身只靠右指针建线索、无栈无递归,无法自然等待左右子树都完成——它只能线性推进。标准解法是先按“根→右→左”走(即逆后序),再把这段路径上刚访问过的节点序列倒过来输出。这个“倒过来”的动作,就落在对左子树最右链的原地翻转上。
关键不是翻转本身难,而是翻转的起止点和恢复逻辑极易出错:翻转段是 curr->left 到前驱 pred(不含 curr)构成的临时右链;终止条件必须是 tail != curr,不是 nullptr;否则会多翻一个节点或提前中断。
翻转链时 prev 必须初始化为 nullptr
这是最隐蔽的崩溃点。翻转循环中:tail->right = prev 这一行依赖 prev 初始为 nullptr,才能让原链尾节点的 right 正确指向空,成为新链头。如果误写成 prev = tail 在循环外先赋值,或漏初始化,首节点的 right 会乱指,后续逆向遍历时直接跳飞或死循环。
-
TreeNode* prev = nullptr;—— 必须显式写,不能省略 - 翻转后
prev指向原链最右下节点,也就是逆后序的第一个节点 - 恢复指针时用
tail->right = prev,不是next;这里写错一个字母,整条链就不可逆
pred->right == curr 是唯一安全的访问时机
中序遍历里,pred->right == nullptr 和 pred->right == curr 分别对应“建线索”和“回溯”,后者就能访问 curr;但后序不行——此时只代表左子树处理完,右子树还没动。所以真正访问 curr 的位置,必须在翻转并输出完左子树链之后,且确保 curr 的右子树也已处理完毕(即 curr 是第二次被访问、且其右孩子已被遍历过)。
立即学习“C++免费学习笔记(深入)”;
实际编码中,这个时机藏在两个条件之后:
-
pred->right == curr成立 → 左子树已走完 - 紧接着执行翻转+输出左子树链 → 把左子树所有后序节点刷进结果
- 最后才轮到
curr自身(但注意:此时还不能直接 push,得等右子树也处理完)
所以完整后序访问点在:翻转输出左链 → 向右走到右子树尽头 → 再沿原路翻转右链 → 最后统一把 curr 补在末尾。更稳妥的做法是把 curr 暂存,等整棵树 Morris 序跑完,再整体 reverse 结果 vector。
恢复指针不彻底会导致后续遍历错乱
Morris 遍历结束后必须还原树结构,否则二次调用会出错。但后序翻转链那段代码里,恢复操作常被忽略或写错位置。
正确顺序是:翻转输出左链时,每访问一个节点,就立刻恢复它的 right 指针:
- 输出
tail前,先执行tail->right = prev - 然后
prev = tail; tail = next; - 这样退出循环时,整条链已复原,
curr->left子树结构完好
漏掉这步,下次从别处进入该子树时,pred->right 可能仍指向某个旧 curr,导致无限循环或访问野指针。尤其在 LeetCode 多测例环境下,一个 case 没恢复,下一个 case 直接崩。


















