Morris遍历

概述

在二叉树遍历的深度优先遍历中，分析了如何用递归和非递归方式实现遍历二叉树，但是那些方法都无法做到空间复杂度为 O(1)，对于递归方法，遍历时用到了函数栈，而对于非递归方法，则是直接申请了栈，这两种方法的空间复杂度均与树的高度相关，设树的高度为 h，则空间复杂度为 O(h)。事实上对于二叉树的遍历，还有一种空间复杂度为 O(1) 的方法，这就是——Morris遍历！！！

普通的递归和非递归解法在遍历过程中，在处理完某个节点后都是通过栈结构（函数栈或申请的栈）才可以返回上层去，正是二叉树的结构（只有从父节点指向孩子节点的指针，而没有从孩子节点指向父节点的指针）导致了从下层回到上层会如此困难。而Morris遍历的实质就是避免使用栈结构实现从下层返回上层，而是使下层到上层有指针，根据下层到上层的指针实现从下层到上层的移动。那么怎么才能有下层到上层的指针呢？

二叉树上的很多节点都有大量的空闲指针（如叶节点就有两个空闲指针），比如某些节点没有右孩子节点，那么这个节点的 right 指针就指向 null，我们将之称为空闲状态，而Morris遍历就是使用了这些空闲指针。

Morris遍历

先不管先序遍历、中序遍历、后序遍历的相关概念，我们先看一下Morris遍历的过程：

设当前节点为 cur，初始 cur = head，则 cur 按照以下规则移动：

• 1.若 cur == null，则过程停止，否则继续下面的过程；
• 2.若 cur 无左子树，则令 cur = cur.right；
• 3.若 cur 有左子树，则找到 cur 左子树上最右的节点，记作 mostRight：
  • 1) 若 mostRight.right == null，则令 mostRight.right = cur，即让 mostRight 的 right 指针指向当前节点 cur，然后令 cur = cur.left；
  • 2) 若 mostRight.right == cur， 则令 mostRight.right = null，即让 mostRight 的 right 指针指向空，然后令 cur = cur.right。

假设有如下的二叉树：

则根据上面的Morris遍历规则，其遍历如下：

（1）初始状态；

（2）cur 来到节点 4，cur 此时有左子树，则找到其左子树的最右节点（即节点 3），发现节点 3 的右指针指向 null，那么让其指向 cur，然后 cur = cur.left；

（3）cur 来到节点 2，cur 此时有左子树，则找到其左子树的最右节点（即节点 1），发现节点 1 的右指针指向 null，那么让其指向 cur，然后 cur = cur.left；

（4）cur 来到节点 1，cur 此时没有左子树，则令 cur = cur.right；

（5）cur 来到节点 2，cur 此时有左子树，则找到其左子树的最右节点（即节点 1），发现节点 1 的右指针指向 cur，则令节点 1 的右指针指向 null，然后令 cur = cur.right；

（6）cur 来到节点 3，cur 此时没有左子树，则令 cur = cur.right；

（7）cur 来到节点 4，cur 此时有左子树，则找到其左子树的最右节点（即节点 3），发现节点 3 的右指针指向 cur，则令节点 3 的右指针指向 null，然后令 cur = cur.right；

（8）cur 来到节点 6，cur 此时有左子树，则找到其左子树的最右节点（即节点 5），发现节点 5 的右指针指向 null，那么让其指向 cur，然后 cur = cur.left；

（9）cur 来到节点 5，cur 此时没有左子树，则令 cur = cur.right；

（10）cur 来到节点 6，cur 此时有左子树，则找到其左子树的最右节点（即节点 5），发现节点 5 的右指针指向 cur，则令节点 5 的右指针指向 null，然后令 cur = cur.right；

（11）cur 来到节点 7，cur 此时没有左子树，则令 cur = cur.right；

（12）cur == null，则过程停止。

经过上述的Morris遍历，cur一次到达的节点值为：4 → 2 → 1 → 2 → 3 → 4 → 6 → 5 → 6 → 7， 我们将这个序列称为Morris序，而且我们可以看出，在Morris遍历的过程中，对于有左子树的节点（4、2、6）都可以到达两次（图中到达两次的节点由粉色标出），而没有左子树的节点都只会到达一次（图中到达一次的节点由黄色标出）

而对于能到达两次的节点（图中粉色节点），我们可以用如下方法判断其是第一次到达，还是第二次到达：

• 如果其左子树的最右节点指向空即 mostRight.right = null，则该节点为第一次到达；
• 如果其左子树的最右节点指向其本身 mostRight.right = cur，则该节点为第二次到达。

Morris遍历的代码如下：

public void morris(TreeNode head) {
    if (head == null) {
        return;
    }
    TreeNode cur = head;
    TreeNode mostRight = null;
    while (cur != null) { // 过程出口
        mostRight = cur.left;
        if (mostRight != null) { // cur有左子树 
            // 找到cur左子树的最右节点
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            // 如果mostRight.right == null，则让其指向cur
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left; // cur左移
                continue; // 回到外层while循环
            } else { // mostRight == cur，则让其指向null
                mostRight.right = null;
            }
        }
        // cur没有左子树或其左子树最右节点指向cur，均要将cur右移
        cur = cur.right;
    }
}

对于Morris遍历，其时间复杂度为O(N)，空间复杂度为O(1)，其中N为二叉树节点个数。

Morris遍历实现深度优先遍历

前序遍历

对于Morris遍历实现前序遍历：

• 对于 cur 只能到达一次的节点（无左子树的节点），cur 到达时直接打印；
• 对于 cur 可以到达两次的节点（有左子树的节点），cur 到达第一次时打印，第二次到达时不打印。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        return morrisMethod(root);
    }

    /**
     * Morris遍历
     * @param root
     * @return
     */
    private List<Integer> morrisMethod(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) { // 到达两次的节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    list.add(cur.val); // 第一次到的时候打印
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null; // 第二次到的时候不打印
                }
            } else { // 到达一次的节点
                list.add(cur.val);
            }
            cur = cur.right;
        }
        return list;
    }
}

中序遍历

对于Morris遍历实现中序遍历：

• 对于 cur 只能到达一次的节点（无左子树的节点），cur 到达时直接打印；
• 对于 cur 可以到达两次的节点（有左子树的节点），cur 到达第一次时不打印，第二次到达时打印。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        return morrisMethod(root);
    }

    /**
     * Morris遍历
     * @param root
     * @return
     */
    private List<Integer> morrisMethod(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) { // 到达两次的节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur; // 第一次到的时候不打印
                    cur = cur.left;
                    continue;
                } else {
                    list.add(cur.val); // 第二次到的时候打印
                    mostRight.right = null; 
                }
            } else { // 到达一次的节点
                list.add(cur.val);
            }
            cur = cur.right;
        }
        return list;
    }
}