C++实现二叉树的Morris前序遍历零辅助空间算法 _ 深度解析【实战】

在二叉树遍历的经典算法中，递归和栈辅助迭代是标准解法，但它们都需要O(n)的额外空间。有没有一种方法，能在不借助栈或递归的情况下，仅用常数额外空间完成遍历呢？答案是肯定的，这就是我们今天要深入探讨的Morris遍历算法。它通过巧妙地“借用”树中节点的空指针来构建临时线索，实现遍历后还能恢复原状，堪称空间优化的典范。下面，我们就聚焦于它的前序遍历版本，拆解其核心思想与实现细节。

一、Morris前序遍历核心思想

Morris遍历的精髓在于“临时借用，用完即还”。它利用树中大量叶子节点存在的空右指针（有时是左指针），在遍历过程中构建出一条条临时的“回溯线索”。对于前序遍历，其核心行动逻辑可以概括为：当你抵达一个节点时，如果它有左子树，那么你首先要访问它自己，然后想办法进入左子树探索，并确保探索完毕后能顺利回来。这个“确保回来”的方法，就是在进入左子树前，先找到左子树中最靠右的那个节点（也就是当前节点在中序遍历下的前驱节点），然后把它的空右指针临时指向当前节点，作为回来的路标。如果节点没有左子树，事情就简单了：访问它，然后直接向右走。

具体来说，算法流程遵循以下步骤：

1. 从根节点出发，将其设为“当前节点”。

2. 只要当前节点不为空，就重复以下判断流程：

3. 如果当前节点没有左孩子，那么按照前序“根左右”的顺序，此时就应该访问它。输出节点值后，转向其右孩子继续。

4. 如果当前节点有左孩子，那么就需要找到它左子树中的“最右节点”。

5. 找到这个最右节点后，检查它的右指针：如果为空，说明我们是第一次来到当前节点，尚未建立回溯线索。这时，我们做三件事：将最右节点的右指针指向当前节点（建立线索），访问当前节点（前序访问），然后将当前节点移动到其左孩子，开始探索左子树。

6. 如果最右节点的右指针已经指向当前节点，这说明左子树我们已经探索完毕，正通过这条线索回溯回来。此时，我们需要“过河拆桥”，将最右节点的右指针重新置为空（恢复树的结构），然后当前节点转向其右孩子，继续主流程。

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

将上述思想转化为代码，关键在于清晰地区分“首次向下探索”和“回溯向上”这两种状态。判断依据就是左子树最右节点的右指针指向谁。整个实现需要像外科手术一样精确，确保指针操作安全，避免内存错误。

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

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

接着，实现前序遍历函数：

vector preorderTra versal(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前序遍历算法就能在不使用任何额外栈空间的情况下，高效、正确地完成遍历任务。它像一位技艺高超的探险家，在森林（二叉树）中探索时，只在必要的岔路口留下临时标记（线索），并在返回时一一擦除，最终不留下任何痕迹，却走遍了每一个角落。