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; } }