C++实现二叉树Morris前序遍历算法详解与实战

在二叉树遍历的经典方法中，递归和基于栈的迭代是标准解法，但它们都需要 O(n) 的额外空间开销。是否存在一种方法，能够在不借助栈或递归的前提下，仅使用常数额外空间完成遍历？答案是肯定的，这正是我们今天要深入剖析的 Morris 遍历算法。该算法通过巧妙地“临时借用”树中节点的空指针来构建线索，遍历完成后还能恢复树的原始结构，堪称空间效率优化的典范。本文将聚焦于其前序遍历版本，详细拆解其核心原理、实现步骤与关键细节。

免费影视、动漫、音乐、游戏、小说资源长期稳定更新！ 👉 点此立即查看 👈

一、Morris前序遍历核心思想

Morris 遍历的精髓在于“临时线索，用完即焚”。它利用二叉树中大量叶子节点存在的空指针（尤其是右指针），在遍历过程中动态构建临时的回溯路径。对于前序遍历，其核心逻辑可概括为：当访问一个节点时，若其存在左子树，则首先访问当前节点（根），然后设法进入左子树探索，并确保探索完成后能顺利返回当前节点。这个“确保返回”的机制，就是在进入左子树前，先找到左子树中最右侧的节点（即当前节点在中序遍历下的直接前驱节点），将其原本为空的右指针临时指向当前节点，作为返回的“线索”。若节点没有左子树，则流程简化：访问当前节点，然后直接转向右子树。

具体而言，算法遵循以下清晰步骤：

1. 初始化当前节点为根节点。

2. 当当前节点不为空时，循环执行以下判断：

3. 若当前节点无左孩子，则按照前序“根左右”的顺序，立即访问该节点。将其值加入结果序列后，当前节点移向右孩子。

4. 若当前节点有左孩子，则需找到其左子树中的“最右节点”。

5. 定位到该最右节点后，检查其右指针：若为空，表明我们是首次抵达此当前节点，尚未建立回溯线索。此时，我们执行三个操作：将最右节点的右指针指向当前节点（建立临时线索），访问当前节点（完成前序访问），然后将当前节点更新为其左孩子，开始探索左子树。

6. 若最右节点的右指针已指向当前节点，则说明左子树已遍历完毕，我们正通过先前设置的线索回溯回来。此时，需“拆除线索”，将最右节点的右指针重新置为空（恢复树形），然后将当前节点转向其右孩子，继续主循环。

二、C++代码实现细节说明

将上述思想转化为 C++ 代码，关键在于精准区分“首次向下探索”与“回溯向上”两种状态，判断依据即为左子树最右节点的右指针指向。实现需确保指针操作严谨，避免形成环或内存访问错误。

首先，定义基础的二叉树节点结构体：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

接下来，实现 Morris 前序遍历的核心函数：

vector preorderTraversal(TreeNode* root) {
    vector result;
    TreeNode* curr = root;

    while (curr != nullptr) {
        if (curr->left == nullptr) {
            // 情况1：无左子树，直接访问根节点并转向右子树
            result.push_back(curr->val);
            curr = curr->right;
        } else {
            // 情况2：有左子树，寻找当前节点的中序前驱节点
            TreeNode* predecessor = curr->left;
            while (predecessor->right != nullptr && predecessor->right != curr) {
                predecessor = predecessor->right;
            }

            if (predecessor->right == nullptr) {
                // 情况2a：首次到达，建立线索并执行前序访问
                predecessor->right = curr;
                result.push_back(curr->val); // 前序访问在此进行
                curr = curr->left;
            } else {
                // 情况2b：通过线索回溯回来，拆除线索并转向右子树
                predecessor->right = nullptr;
                curr = curr->right;
            }
        }
    }
    return result;
}

代码中查找前驱节点的 while 循环是核心，条件 predecessor->right != nullptr && predecessor->right != curr 确保它准确停在真正的最右节点，且不会因已存在的线索而陷入无限循环。

三、关键边界情况处理

一个健壮的算法必须妥善处理各类边界场景。对于 Morris 前序遍历，需特别注意以下几点：

1. 空树处理：若输入根节点为 nullptr，函数直接返回空结果容器，外层循环不会执行，处理正确。

2. 前驱查找的安全性：查找 predecessor 的循环条件至关重要。必须同时检查右指针非空且不指向当前节点，才能准确定位到真正的最右叶子或已线索化的节点。

3. 访问节点的时机：这是 Morris 前序遍历与中序遍历的主要区别。节点值必须在“建立线索”的同时（即第一次到达该节点时）加入结果集，这严格遵循了前序遍历“根-左-右”中先访问根节点的规则。

4. 树结构的恢复：当通过 predecessor->right == curr 判断处于回溯状态时，必须先将 predecessor->right 恢复为 nullptr，再移动当前节点。此顺序保证了树的原始结构在遍历中被即时修复，不会遗留错误指针或影响后续操作。

5. 避免重复访问：算法设计保证了每个节点最多被处理两次（一次向下，一次回溯），但其值仅被输出一次（在无左子树或首次建立线索时）。仔细跟踪流程可确认，回溯路径上的节点不会再次将其值加入结果，确保了正确性。

通过以上步骤，Morris 前序遍历算法便能在不使用任何递归调用或显式栈辅助的情况下，高效、准确地完成二叉树遍历。它如同一位技艺精湛的探险家，在森林（二叉树）中穿行时，只在关键岔路口留下临时标记（线索），并在返回时逐一清除，最终不露痕迹地踏遍每一处角落，实现了空间复杂度的极致优化。