C++实现二叉树的Morris遍历 _ 空间复杂度O(1)的遍历技巧【实战】-C++-PHP中文网

morris遍历的核心思想是利用二叉树中空闲的右指针临时建立线索，指向中序后继节点，遍历完成后恢复原结构，实现o(1)空间复杂度；其关键操作包括找左子树最右节点、判断并建立/拆除线索、按需访问节点。

c++实现二叉树的morris遍历 _ 空间复杂度o(1)的遍历技巧【实战】

Morris遍历的核心思想：用空指针“借道”做线索

Morris遍历不是靠栈或递归，而是临时修改二叉树结构，把原本指向 null 的右指针（对左子树而言）或左指针（对右子树而言）重定向为“线索”，指向中序/前序的后继节点。遍历完再恢复原状——空间复杂度真正压到 O(1)，连函数调用栈都不用（非递归版需显式栈，递归版隐式栈仍是 O(h)）。

关键前提：所有节点的 right 指针在初始时都可能为空；我们只利用这些“闲置”指针临时建立线索，且保证每条线索最多被使用两次（建立 + 拆除），不会漏节点、不破坏逻辑顺序。

中序遍历的Morris实现：三步循环 + 一次回溯

核心是找当前节点 cur 的前驱（inorder predecessor）：即左子树最右节点。如果前驱的 right 是空，就把它指向 cur，然后向左走；如果已指向 cur，说明左子树已处理完，输出 cur->val，断开线索，向右走。

每次进入左子树前，必须先找前驱：用 pred = cur->left，再循环 while (pred->right && pred->right != cur) pred = pred->right
若 pred->right == nullptr：建立线索 pred->right = cur，cur = cur->left
若 pred->right == cur：恢复结构 pred->right = nullptr，访问 cur，cur = cur->right
注意边界：当 cur 为 nullptr 时循环结束，无需额外判空入口

示例片段（中序）：

while (cur) {
    if (!cur->left) {
        res.push_back(cur->val);
        cur = cur->right;
    } else {
        TreeNode* pred = cur->left;
        while (pred->right && pred->right != cur) pred = pred->right;
        if (!pred->right) {
            pred->right = cur;
            cur = cur->left;
        } else {
            pred->right = nullptr;
            res.push_back(cur->val);
            cur = cur->right;
        }
    }
}