C++如何实现二叉树的 Morris 后序遍历算法-C++-PHP中文网

morris后序遍历的核心难点在于后序天然依赖回溯，而morris线索仅支持单向回跳，无法直接捕获“右子树访问完毕、该处理根”的时机，故需通过构造“根→右→左”遍历并翻转右链来模拟后序，涉及复杂指针操作与易错的链表翻转。

c++如何实现二叉树的 morris 后序遍历算法

Morris 后序遍历的核心难点在哪

Morris 遍历用线索化代替栈/递归，空间复杂度压到 O(1)。但后序（左→右→根）天然依赖“回溯”，而 Morris 的线索只提供单向回跳（从子节点跳回父节点），没法直接拿到“刚访问完右子树、该处理根了”这个时机。所以不能像前序/中序那样边走边输出，必须把节点暂存起来反向输出——本质是“逆序的前序”：根→右→左的遍历结果翻转，就等于左→右→根。

这意味着你得在遍历过程中收集节点，最后一次性倒序打印；或者边走边局部翻转链表来模拟倒序输出。后者更省内存，也更贴近经典 Morris 实现思路。

如何构造“根→右→左”的 Morris 遍历

这是后序的底层骨架。关键在于把标准 Morris 中序的「左子树线索指向 root」逻辑，改成「右子树线索指向 root」，并调整移动方向：

从 root 开始，每次优先往 right 走（不是 left）
若当前节点 cur 无右孩子，直接加入暂存序列（或翻转输出），然后跳到 cur->left
若有右孩子，则找其左子树最左节点（即 cur->right 的“最左后代”），设为 pre
若 pre->left == nullptr，建立线索：pre->left = cur，然后 cur = cur->right
若 pre->left == cur，说明右子树已处理完，断开线索：pre->left = nullptr，此时将 cur 到 pre 这一段右链上的所有节点**逆序输出**（即从 cur 沿 right 链走到 pre，再反向遍历），然后 cur = cur->left

注意：这里用的是 right 子树 + left 线索，和中序（left 子树 + right 线索）完全对称。别混淆左右方向。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

为什么必须翻转右链，而不是直接存 vector 再 reverse

理论上存 vector<treenode></treenode> 最后 reverse() 是可行的，但违背了 Morris 的初衷：它要求 O(1) 额外空间（不计输出空间）。用 vector 就变成 O(h) 或 O(n) 空间。

真正符合定义的做法是：当检测到一个右子树已处理完毕（即遇到已存在的线索），就沿着 cur → cur->right → cur->right->right → ... → pre 这条临时链，用头插法或三次反转实现局部逆序输出：

// 伪代码：翻转并输出 cur 到 pre 的右链
TreeNode* head = cur;
TreeNode* tail = pre;
TreeNode* prev = nullptr;
while (head != tail) {
    TreeNode* next = head->right;
    head->right = prev;
    prev = head;
    head = next;
}
// 此时 head == tail，再把 tail->right = prev 完成整段翻转
// 然后从 tail 开始沿 right 遍历输出（即原顺序的逆）

这段链表翻转是 Morris 后序最易出错的部分：指针操作多、边界易漏（比如没处理 tail->right）、翻转后忘记恢复（虽然输出完就丢弃，但调试时容易混乱）。