C++ 实现二叉树的 Morris 后序遍历算法及其零辅助空间路径翻转【实战】-C++-PHP中文网

Morris后序遍历必须翻转路径，因为原树right指针被用作线索导致无法自然实现“左右根”顺序；需就地翻转pre到cur的临时右链以反向访问，访问后再翻转恢复。

c++ 实现二叉树的 morris 后序遍历算法及其零辅助空间路径翻转【实战】

为什么 Morris 后序遍历必须翻转路径

Morris 后序遍历不是前序/中序的简单改写，核心卡点在于：后序要求「左右子树都访问完再处理根」，而 Morris 的线索化本质是用右指针临时指向回溯路径——但原树中根节点的 right 指针在遍历时可能已被改写为线索，无法自然支撑「先右再根」的顺序。所以必须把从当前节点到其前驱构成的单向链（即临时右链）**就地翻转**，使能按「子→父」反向访问；访问完再翻回来，恢复树结构。

翻转路径时容易漏掉的三个边界条件

路径翻转看似只是链表反转，但在 Morris 场景下极易出错：

翻转起点不是 cur，而是 pre（前驱），终点是 cur 本身——因为翻转的是 pre 沿右指针一路走到 cur 的整条临时链
当 cur->left == nullptr 时，不走 Morris 流程，直接跳过翻转，但需仍输出该节点值（后序中它是叶子，应最先被访问）
翻转后的访问循环必须用 do-while，不能用 while：因为即使 pre == cur（即无右子树、无线索），也要至少访问一次 cur

`reversePath()` 函数的正确写法与副作用控制

这个辅助函数必须满足：只翻转指定路径、不修改节点原始左指针、返回翻转后链尾（即原链头）以便后续恢复。常见错误是翻转时误改 node->left 或未保存原始 next 导致链断裂：

TreeNode* reversePath(TreeNode* from, TreeNode* to) {
    TreeNode* prev = nullptr;
    TreeNode* curr = from;
    while (prev != to) {
        TreeNode* next = curr->right;  // 只动 right，left 必须不动
        curr->right = prev;
        prev = curr;
        curr = next;
    }
    return prev; // 返回翻转后的头（即原 to 节点）
}

调用后必须立刻用相同逻辑再翻转一次恢复——否则下一轮 Morris 会因 right 指针错乱而崩溃。

C++14

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

下载

完整 Morris 后序遍历的主循环关键判断点

主循环里真正决定行为的只有两个分支，其余全是翻转与恢复的机械操作：

若 cur->left == nullptr：说明无左子树，cur 是叶子或右倾路径起点，直接访问它，然后 cur = cur->right
若 cur->left != nullptr：找前驱 pre，分两种情况：
- 前驱 right 为空 → 建线索：pre->right = cur，cur = cur->left
- 前驱 right == cur → 线索已存在，说明左子树已处理完，此时：
  1. 翻转 pre 到 cur 的路径
  2. 沿翻转后链访问所有节点（含 cur）
  3. 再翻转一次恢复原路径
  4. 清空线索：pre->right = nullptr
  5. cur = cur->right