Morris是一种二叉树的遍历方式。对于二叉树的遍历，通常有前序、中序、后序遍历三种方式。

前序遍历

前序遍历就是优先遍历二叉树的根结点，然后左节点，然后右节点。
以下图二叉树为例，前序遍历的结果是

image.png

1，2，4，8，9，5，3，6，10，7
可以很容易的用递归把代码写出来

  1. def preorder(root):
  2.     if root:
  3.         print(root.val)
  4.         preorder(root.left)
  5.         preorder(root.right)

在最坏的情况下，树是单叉树，因此时间复杂度是O(n),使用了递归开辟了栈空间， 空间复杂度是O(n)

一般而言，可以用递归就可以用迭代实现，在递归中，天然的调用栈帮我们保存了“回去的路”。在迭代中，我们需要自己创建栈来保存。

  1. def preorder(root):
  2.     stack = []
  3.     node = root
  4.     while stack or node:
  5.         while node:
  6.             print(node.val)
  7.             stack.append(node)
  8.             node = node.left
  9.         node = stack.pop()
  10.         node = node.right

时间复杂度是O(n)空间复杂度为O(n)

Morris遍历

下面来说Morris遍历。在上面的遍历方式中，我们使用了栈来保存”回去的线索”。在Morris遍历中不需要使用栈，而是使用树的空闲指针保存回去的线索。
Morris前序遍历的规则总结如下

  1. 新建临时节点，令该节点为 root；
  2. 如果当前节点的左子节点为空，将当前节点加入答案，并遍历当前节点的右子节点；
  3. 如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点：
    • 如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案，当前节点更新为当前节点的左子节点。
    • 如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。当前节点更新为当前节点的右子节点。
  4. 重复步骤2和步骤3，直到遍历结束

那么这么一串东西说的什么呢，其实他说的就是如何找线索，如图所示。
image.png
那么如何找中序遍历下的前序节点呢,规则如下。

  • 如果该节点有左节点，从左节点开始
    • 如果左节点有右节点，沿着右节点一直走到底，得到的就是前驱节点 （比如5是2的前驱节点)
    • 如果左节点没有右节点，那么左节点就是前驱节点（比如8是4的前驱节点）
  • 如果该节点没有左节点
    • 如果当前节点是父节点的的左节点，那么他没有前驱节点（比如9）
    • 如果是父节点的右节点，那么她的前驱节点就是父节点（比如10的前驱节点是6）

前驱节点的右指针一定是空的
前序遍历的参考代码如下

  1. def preorder(root):
  2.     p1 = root
  3.     while p1:
  4.         p2 = p1.left
  5.         if p2:
  6.             while p2.right and p2.right != p1:
  7.                 p2 = p2.right
  8.             if not p2.right:
  9.                 print(p1.val)
  10.                 p2.right = p1
  11.                 p1 = p1.left
  12.                 continue
  13.             else:
  14.                 p2.right = None
  15.         else:
  16.             print(p1.val)
  17.         p1 = p1.right

当然这样比正常使用栈去记录线索会多遍历几次，也体现了空间换时间的思想。