Morris Traversal

Morris 遍历利用二叉树中原本为空的右指针建立临时线索，在不使用递归栈的情况下完成遍历。时间复杂度为 $O(n)$，额外空间为 $O(1)$，结束后树结构会恢复。

中序遍历

对当前节点 cur：

1. 若没有左子树，访问 cur，转向右子树；
2. 否则找到左子树最右侧节点 pred；
3. 若 pred.right 为空，令它指向 cur，然后进入左子树；
4. 若 pred.right == cur，说明左子树已经遍历完成，断开线索、访问 cur，进入右子树。

void morrisInorder(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            visit(cur);
            cur = cur.right;
            continue;
        }

        TreeNode pred = cur.left;
        while (pred.right != null && pred.right != cur) {
            pred = pred.right;
        }

        if (pred.right == null) {
            pred.right = cur;
            cur = cur.left;
        } else {
            pred.right = null;
            visit(cur);
            cur = cur.right;
        }
    }
}

每条临时边最多被创建和删除一次，因此寻找前驱的总成本仍为 $O(n)$。实际使用时必须保证异常或提前返回不会留下未恢复的线索。

前序遍历可把访问时机移动到第一次遇到节点；后序遍历则需要虚拟根节点和逆序访问右边界，复杂度更高。