二叉树的 morris 遍历

1. 背景介绍

对于二叉树，常用的遍历方式有前序遍历、中序遍历、后序遍历。借由 DFS 算法，我们可以在 O(n) 时间内、使用 O(h) 的空间完成遍历。这通常没什么问题，但如果有特殊要求 O(1) 的空间，那可以采用 Morris 遍历算法。

Morris 遍历算法可以在 O(n) 时间内使用 O(1) 的空间完成遍历，但需要对二叉树进行修改（遍历完成后恢复原样）。

2. 算法思想简介

Morris 算法的思想如下：

当我们遍历到一棵树时，考虑其根节点 root 的 直接前驱(predecessor)，即左子树的最右节点，记为 pred。由其定义，pred 的右子节点一定为空。如果我们将 pred 的右子节点指向 root，那么就可以在遍历完左子树后，回到 root 而不使用额外的栈空间。

使用伪代码描述遍历：

while root != null {
    if root.left == null {
        // no left tree, visit root here
        root = root.right;
        continue;
    }
    pred = find_pred(root);
    if pred.right == root {
        // just finished visit left tree.
        pred.right = null;
        root = root.right;
    } else {
        // just about to visit left tree.
        pred.right = root;
        root = root.left;
    }
}

3. 复杂度分析

• 空间复杂度：显然为 O(1)。

• 时间复杂度：对于每棵树，其会查找两次前序，左右树各遍历一次，因此有： $$\begin{aligned} f(n) &= f(n_{l}) + f(n_{r}) + 2 f_p(root) + O(1) \\ &= \sum_n {f(1)} + 2 \sum_{node}{f_p(node)} \\ \end{aligned}$$ 注意到，$f_p(root)$ 代表寻找点 $root$ 的直接前驱节点的复杂度，而对每个节点都查找其前驱节点的复杂度总和为 $O(n)$，因此

$$\begin{aligned} f(n) &= \sum_n {f(1)} + 2 \sum_{node}{f_p(node)} \\ &= O(n) + O(n) \\ &= O(n) \end{aligned}$$

故其总时间复杂度也为 O(n)。

4. 细节问题

注意到伪代码中的几个注释为插入代码的部分，可以在

• 缺少左子树时
• 将要遍历左子树之前
• 遍历完左子树之后

进行操作。对于前序遍历和中序遍历，都可以在这三处插入代码实现。

对于后序遍历，需要在 pred.right == root 处，倒序输出从 root.left 到 pred 的路径。另外需要将 root 设置为一个 fake_root 的左节点。