C++如何实现二叉树的Morris前序遍历（O(1)空间）-C++-PHP中文网

morris前序遍历的核心逻辑是：在首次抵达每个节点时立即访问（“见根即访”），利用左子树最右节点的空right指针建立临时线索，有左子树时于建线前输出、无左子树时直接输出并右移，确保“根→左→右”顺序且线索建拆各一次、树结构最终恢复。

c++如何实现二叉树的morris前序遍历（o(1)空间）

Morris前序遍历的核心逻辑是什么？

Morris遍历的本质是用二叉树中原本为空的 right 指针（或 left，取决于方向）临时“链接”回祖先节点，从而避免使用栈或递归。前序遍历要求在第一次访问节点时就输出值，这和中序不同——中序是在“回溯”到某节点时输出，而前序必须抓住“首次抵达”的时机。

关键判断点：当从左子树绕回当前节点时，那个临时链接（predecessor->right == curr）意味着这次是第二次来，要拆除链接；而第一次来时，predecessor->right 是 nullptr，此时应先输出 curr->val，再建立链接并左移。

如何避免重复访问和漏输出？

常见错误是把前序输出位置放错：有人在建立线索后立刻输出，结果导致右子树根被提前输出；也有人只在无左子树时输出，漏掉有左子树但已完成线索遍历的节点。

正确做法是统一在两个地方输出：

当节点没有左子树时，直接输出 curr->val，然后向右走
当有左子树，且找到前驱（predecessor）后，若 predecessor->right 为 nullptr，说明是首次到达，此时输出 curr->val，再设 predecessor->right = curr，然后向左走
若 predecessor->right == curr，说明已遍历完左子树，此时**不输出**，只恢复空链接（predecessor->right = nullptr），然后向右走

注意：输出动作永远发生在“准备向左深入”之前，而不是“从左回来之后”。

C++14

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

下载

C++实现中指针操作的易错点

C++里最容易出问题的是指针判空和链接复位：

找前驱时，必须用 while (pred->right && pred->right != curr)，漏掉 pred->right != curr 会导致死循环（比如右链已连回自己）
建立线索前必须确认 pred->right == nullptr，否则可能覆盖已有链接（尤其在多轮遍历中）
复位时写成 pred->right = nullptr，不是 curr->right = nullptr —— 错对象会破坏树结构
移动 curr 的逻辑必须严格对应：无左子树 → 向右；有左且首次 → 输出 + 左移；有左且二次 → 复位 + 右移

示例片段（核心循环节）：

while (curr) {
    if (!curr->left) {
        result.push_back(curr->val);
        curr = curr->right;
    } else {
        TreeNode* pred = curr->left;
        while (pred->right && pred->right != curr) {
            pred = pred->right;
        }
        if (!pred->right) {
            result.push_back(curr->val); // ← 前序输出在此
            pred->right = curr;
            curr = curr->left;
        } else {
            pred->right = nullptr;
            curr = curr->right;
        }
    }
}