多看几眼就会的Morris遍历：原理和实现

11次阅读

共计 3404 个字符，预计需要花费 9 分钟才能阅读完成。

1.算法介绍

对一个二叉树进行前序、中序、后序遍历，最常见的方法分为两种：递归和迭代，这两种方式的时间复杂度都为 $O(n)$ ，效率都是非常高的。

递归由于需要递归过程中栈的开销，所以空间复杂度为 $O(h)$ (h为二叉树的高度)，而迭代直接显示地模拟了一个栈，所以空间复杂度也是 $O(h)$ 。

其实这两种遍历方法都已经相当不错了，但在1960-1970年代，计算机内存资源极度稀缺（早期计算机内存仅KB级别），这些方案都存在了内存瓶颈。

此前，1960年Perlis & Thornton提出了线索二叉树（Threaded Binary Tree)的思路，即通过在节点中增加额外指针（线索）记录前驱/后继节点，实现无栈遍历，但该方案需要修改节点结构、新增存储，并非真正意义上的 $O(1)$ 空间复杂度。

终于在1979年，Joseph M. Morris 在论文中首次提出了Morris遍历，实现了线性时间、常数空间的二叉树遍历。

Morris遍历支持二叉树的前序、中序、后序三种遍历方式，但后序遍历在实现上稍显繁琐，需额外处理右边界逆序打印，可作为进阶内容掌握。

2.算法原理

Morris遍历的核心是复用了二叉树中大量的空闲的右指针(right)，临时建立回溯线索。以下是Morris遍历的核心机制：

对每个有左子树的当前节点 cur , 找到其左子树的最右节点 pre ；
若 pre->right 指向 NULL，则将其临时指向 cur建立线索，进入左子树；
若 pre->right指向 cur 当前节点，则访问 cur 并拆除线索，进入右子树。

上述本质就是将树自身的空闲指针替代栈，实现了无额外空间的回溯。

下面让我们来实际感受一下具体过程：

上述二叉树的中序遍历顺序为 1->2->3->4->6->5->7,下面用Morris遍历是逐步骤拆解全过程。

初始化 cur 为根节点 root, cur有左子树，找到左子树的最右节点—节点3，节点3的right指针指向NULL，表示这是第一次来到节点3。建立线索 pre->right = cur; 即节点3的右指针指向节点4。

2. 接着cur向左移动，来到节点2。此时cur节点有左子树，找到左子树的最右节点—-节点1，节点1的右指针指向NULL，表示这是第一次来到节点1，建立线索，使得节点1的右指针指向 cur。

3. cur继续向左移动，来到节点1。由于节点1没有左子树，所以向右移动，通过刚建立的线索 cur 回到了节点2。

4. 此时由于cur所在的节点2有左子树，找到左子树的最右节点—节点1，发现最右节点指向当前节点 cur,说明已经是第二次来到节点1的位置，将线索拆除，即将节点1的right指针指向NULL ，恢复树结构。

5. 接着cur向右移送，来到节点3。发现节点3没有左子树，继续向右移动，来到节点4。

6. 节点4有左子树，找到左子树最右节点—节点3，发现节点3的右指针指向自己，说明已经遍历过了，将节点3的右指针指向NULL，还原树结构。此时该二叉树的左子树已经遍历完毕。

7. cur向右移动，来到节点5。节点5有左子树，其最右节点为节点6，发现节点6的右指针指向NULL，说明这是第一次来到节点6，建立线索，将right指针指向节点5。

8. cur向左移动，来到节点6，节点6没有左子树，向右移动，再次来到节点5。发现左子树的最右节点节点6的右指针指向自己，说明已经遍历过节点6，消除线索，cur指针向右移动，来到了节点7。

9. 节点7没有左子树，也没有右孩子，遍历结束。

以上就是Morris遍历的全过程了，从中可以总结出以下几条规则：

当cur没有左孩子时，cur向右移动。
当cur有左孩子时，找到其最右节点。
- 如果最右节点的right指针指向NULL,则建立线索，使其指向cur，cur向左遍历。
- 如果最右节点的right指针指向cur，则还原树结构，使其重新指向NULL，cur向右遍历。

如何实现前、中、后序遍历：

如果你在建立线索的时刻打印访问节点。那这就是前序遍历；
如果你在销毁线索的时候打印访问节点，这就是中序遍历；
如果你想要后序遍历，则需要在销毁线索的时候 “逆序打印左子树的右边界” ，最后单独处理根节点的右边界。

3.代码实现

    //前序遍历
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        while (root) {
            if (root->left) {
                TreeNode* mostRight = root->left;
                while (mostRight->right && mostRight->right != root) {
                    mostRight = mostRight->right;
                }
                if (mostRight->right == nullptr) {
                    ans.emplace_back(root->val);
                    mostRight->right = root;
                    root = root->left;
                    continue;
                }
                mostRight->right = nullptr;
            } else {
                ans.emplace_back(root->val);
            }
            root = root->right;
        }
        return ans;
    }

    //中序遍历
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        while (root) {
            if (root->left) {
                TreeNode* pre = root->left;
                while (pre->right && pre->right != root) {
                    pre = pre->right;
                }
                if (pre->right == nullptr) {
                    pre->right = root;
                    root = root->left;
                    continue;
                }
                else{pre->right = nullptr;}
            }
            ans.push_back(root->val);
            root = root->right;
        }
        return ans;
    }

class Solution {
private:
    TreeNode* reverse(TreeNode* from) {
        TreeNode* pre = nullptr;
        TreeNode* nxt = nullptr;
        while (from) {
            nxt = from->right;
            from->right = pre;
            pre = from;
            from = nxt;
        }
        return pre;
    }

    void Collect(TreeNode* from, vector<int>& ans) {
        TreeNode* tail = reverse(from);
        TreeNode* cur = tail;
        while (cur) {
            ans.emplace_back(cur->val);
            cur = cur->right;
        }
        reverse(tail);
    }

public:
    //后序遍历
    vector<int> postorderTraversal(TreeNode* root) {
        TreeNode* head = root;
        vector<int> ans;
        while (root) {
            if (root->left) {
                TreeNode* mostRight = root->left;
                while (mostRight->right && mostRight->right != root) {
                    mostRight = mostRight->right;
                }
                if (mostRight->right == nullptr) {
                    mostRight->right= root;
                    root = root->left;
                    continue;
                }
                mostRight->right = nullptr;
                Collect(root->left, ans); 
            }
            root = root->right;
        }
        Collect(head, ans);
        return ans;
    }
};

可在下方leetcode的对应链接中测试代码。

前序遍历：https://leetcode.cn/problems/binary-tree-preorder-traversal/description

中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

正文完

发表至：算法

近一天内

1