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

morris中序遍历以o(1)额外空间实现，核心是利用左子树最右节点的空右指针临时链接回当前节点；访问时若无左子树则直接输出并右移，否则找前驱、打链（未打过）或还原+输出+右移（已打过），必须配对还原右指针以保树结构。

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

Morris中序遍历的核心思想是用叶子节点的空右指针“临时链接”回祖先，避免递归栈或显式栈

它不新建任何容器，也不递归，真正实现 O(1) 额外空间（除输出结果外）。关键在于：当访问到某个节点 cur 时，如果它没有左子树，直接输出并走右；否则，先找到它的**左子树最右节点**（即中序前驱），把该前驱的右指针临时指向 cur，然后向左走——这步“打链”是可逆的，后续会还原。

如何判断是否已打过链？看左子树最右节点的右指针是否指向当前节点

这是 Morris 遍历最易错的逻辑分支。对每个 cur，先找其左子树的最右节点 pre（即 pre = cur->left; while (pre->right && pre->right != cur) pre = pre->right;）：

若 pre->right == nullptr：说明还没打链，执行 pre->right = cur，然后 cur = cur->left
若 pre->right == cur：说明已打过链、现在是“回溯回来”，此时应恢复树结构（pre->right = nullptr），输出 cur，再向右走（cur = cur->right）

C++ 实现中必须手动还原右指针，否则破坏原树结构

很多初学者只关注遍历顺序，忽略还原步骤，导致二次遍历出错或调试时树被改坏。注意以下几点：

C++14

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

下载

所有对 pre->right 的赋值都要配对还原（仅在 pre->right == cur 分支里还原）
不能在 cur 为 nullptr 时访问 cur->left，循环条件应为 cur != nullptr
输出时机只在“回溯路径”上：即确认 pre->right == cur 后、还原前
示例片段（非完整类，仅主干）：

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    TreeNode* cur = root;
    while (cur) {
        if (!cur->left) {
            res.push_back(cur->val);
            cur = cur->right;
        } else {
            TreeNode* pre = cur->left;
            while (pre->right && pre->right != cur) pre = pre->right;
            if (!pre->right) {
                pre->right = cur;
                cur = cur->left;
            } else {
                pre->right = nullptr;  // 必须还原！
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
    }
    return res;
}
</int></int>

与递归/栈版本对比：Morris 不支持中途 break，且无法自然获取父节点信息

如果你需要在遍历中根据条件提前退出（比如找第一个大于 x 的值），Morris 虽然能做，但逻辑会变复杂——因为“打链”和“还原”耦合在流程里，中断后可能留脏状态。另外，它完全不暴露调用栈或父指针，想在访问某节点时知道它是谁的左/右孩子，得额外记录（比如用哈希表缓存父子关系，但这破环了 O(1) 空间承诺）。

真正节省空间的代价，是牺牲了遍历过程中的上下文可见性。写完别忘了跑个 nullptr 输入和单节点树验证边界——这两处最容易漏判空指针。