C++ 实现二叉树的 Morris 后序遍历 _ 零辅助空间与路径翻转逻辑【实战】-C++-PHP中文网

Morris后序遍历更难写，因其需在第二次访问节点时逆序输出左子树的“右链”，必须显式翻转并还原单向链表；而前序/中序仅需标记或简单访问，无需链表操作。

c++ 实现二叉树的 morris 后序遍历 _ 零辅助空间与路径翻转逻辑【实战】

为什么 Morris 后序遍历比前序/中序更难写

Morris 遍历的核心是用叶子节点的空右指针“临时挂载”回溯路径，但后序要求左右子树访问完才处理根——这意味着你得在第二次经过某个节点时，**逆序输出从它的左孩子到当前节点的整条“右链”**。这不是简单打个标记就能搞定的事，而是必须显式翻转一段单向链表。

常见错误现象：nullptr 访问、重复访问某节点、漏掉根节点、或输出顺序完全错乱。根本原因往往是没真正理解“翻转右链”的触发时机和边界条件。

只有当 cur->left != nullptr 且已建立过 predecessor->right == cur 的回边时，才进入翻转逻辑
翻转起点是 cur->left，终点是 cur（不含 cur 自身）
翻转后要再遍历一遍该链输出，然后还原指针——否则下一轮会断链

关键函数：reverseAndPrint 与指针还原

这个辅助函数不光要翻转，还得边翻转边输出，并在退出前把链表恢复原状。它不是纯工具函数，而是 Morris 后序的“心脏”。

实操建议：

输入参数必须是 from（起始节点，即 cur->left），不能传 cur
翻转过程中用三指针：prev、curr、next；每次翻转前先 std::cout val
翻转结束后，prev 指向原链尾（即最右节点），此时需将它的 right 设为 nullptr，否则下次遍历时会误入死循环
别忘了在函数末尾把整条链再翻回去——用同样三指针再翻一次即可

示例片段（核心逻辑）：

void reverseAndPrint(TreeNode* from) {
    TreeNode *prev = nullptr, *curr = from, *next;
    while (curr) {
        next = curr->right;
        curr->right = prev;
        std::cout val right;
        curr->right = prev;
        prev = curr;
        curr = next;
    }
}

主循环里何时调用 reverseAndPrint

只在两种情况下需要翻转输出：

C++14

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

下载

cur->left != nullptr 且 predecessor->right == cur（即第二次抵达该节点）→ 这是翻转的唯一信号
cur->left == nullptr 时，直接输出 cur->val，不翻转

容易踩的坑：

把 cur->left == nullptr 的情况也塞进翻转逻辑，导致空指针解引用
在 predecessor->right = cur 后立刻翻转（那是第一次路过，左子树还没遍历完）
翻转后忘记把 predecessor->right 重置为 nullptr，后续 Morris 结构被污染

所以主循环中关键判断长这样：

if (cur->left == nullptr) {
    std::cout val right;
} else {
    TreeNode* pred = cur->left;
    while (pred->right && pred->right != cur) pred = pred->right;
    if (pred->right == nullptr) {
        pred->right = cur;
        cur = cur->left;
    } else {
        pred->right = nullptr; // 先断链
        reverseAndPrint(cur->left); // 再翻转输出左子树的“右链”
        std::cout val right;
    }
}