Morris 二叉树遍历算法

简介

Morris 是一个能够在 $O(2n)$ 时间复杂度，$O(1)$ 空间复杂度 下完成 二叉树遍历 的算法。它的思想是 用时间换空间，用二叉树 冗余指针存储遍历状态 。

一些术语

前驱节点: 二叉树遍历过程中，节点 $x$ 的 上一个 遍历到的节点

后继节点: 二叉树遍历过程中，节点 $x$ 的 下一个 遍历节点

最右节点: 子树 $x$ 中，一直往 $x.right$ 走，直到 $x.right=$ null 为止

本质

Morris 动态维护 后继节点，通过不断找到 后继节点 实现遍历。假设当前遍历到子树 $x$

  1. 如果 $x$ 的 左子树 为空，那么 后继节点 即为 $x.right$，遍历 右子树 $x.right$
  2. 如果 $x$ 的 左子树 不为空
    1. 假如 $x.left$ 没被遍历 过，那么 后继节点 即为 $x.left$，遍历 左子树 $x.left$
    2. 假如 $x.left$ 被遍历 过，那么 后继节点 即为 $x.right$，遍历 右子树 $x.right$

Morris 需要解决两个问题

  1. 在遍历完 左子树 $x.left$ 后，如何找到 后继节点 $x.right$

    左子树 $x.left$ 的 最右节点 $right$，就是 $x.left$ 遍历的最后一个节点。由于 $right.right$= null，可以直接将 $right.right=x$，从而 $right.right.right$ 就是 后继节点。

  2. 如何判断 $x.left$ 是否被遍历过

    如果 左子树 的 最右节点 $right$ 中，$right.right \neq$ null，说明 已遍历过了。判断完应该恢复为 $right.right=$ null，删除子树 $x.left$ 是否被遍历的状态，防止下一次遍历出问题。

时间复杂度分析

Morris 中每个子树的 右节点 $x.right$ 最多会被经过 2 次，左节点 最多会被经过 1 次，因此 时间复杂度 为 $O(2n)$。Morris 没有使用任何额外的空间，因此 空间复杂度为 $O(n)$

例题 173. 二叉搜索树迭代器

通过 Morris 的思想，实现中序遍历即可。

class BSTIterator {
    TreeNode current;

    public BSTIterator(TreeNode root) {
        current = root;
    }

    public int next() {
        int value = 0;
        while (current != null) {
            if (current.left == null) {
                value = current.val;
                current = current.right;
                break;
            } else {
                TreeNode last = current.left;
                while (last.right != null && last.right != current) {
                    last = last.right;
                }
                
                if (last.right == null) {
                    last.right = current;
                    current = current.left;
                } else {
                    last.right = null;
                    value = current.val;
                    current = current.right;
                    break;
                }
            }
        }
        return value;
    }

    public boolean hasNext() {
        return current != null;
    }
}