额外空间复杂度O(1) 的二叉树遍历 → Morris Traversal，你造吗？

​

​

前情回顾

二叉树的遍历 → 不用递归，还能遍历吗中讲到了二叉树的深度遍历的实现方式：递归、栈+迭代

　　不管采用何种方式，额外空间复杂度都是 O(N)

　　那有没有额外空间复杂度 O(1) 的遍历方式了？

　　很早之前就被人给专研出来了，也就是本文的主角：Morris Traversal

Morris Traversal

　　因为它由 Joseph Morris 发明的，所以叫 Morris Traversal

　　递归、栈+迭代的遍历，本质都是使用了栈结构进行辅助，所以在处理完某个节点后能回到上层去

　　二叉树的结构决定了它从上层到下层（根到叶子）很容易，但从下层到上层却很难，因为只有父节点指向子节点的指针，而没有子节点指向父节点的指针

　　Morris 遍历的实质就是避免使用栈结构，而是让下层到上层有指针，通过底层节点指向 null 的空闲指针指向上层的某个节点，从而实现下层到上层的移动

　　空闲指针从哪来？二叉树的叶子节点，或者只有单个孩子的节点（左指针空闲或右指针空闲）

　　具体实现，我们往下看

　　移动规则

　　也就是遍历过程；设当前节点为 cur ，初始 cur = root ，则 cur 的移动规则如下

　　1、如果 cur 没有左子树，则让 cur 向右移动，即 cur = cur.right

　　2、如果 cur 有左子树，则找到 cur 左子树最右的节点，记作 mostRight

　　　　2.1、如果 mostRight 的右指针指向 null ，让其指向 cur ，然后 cur 向左移动

　　　　2.2、如果 mostRight 的右指针指向 cur ，让其指向 null ，然后 cur 向右移动

　　3、当 cur 为 null 时，遍历停止

　　这描述还是有点抽象，我们结合具体的二叉树，利用移动规则把二叉树遍历一遍

　　初始二叉树如下

　　1）初始 cur 在节点 a，此时 cur 有左子树，找到其左子树的最右节点，即节点 k，k 的右指针指向 null ，让其指向 cur ，然后 cur 左移

　　　　此时二叉树结构如下， cur 第一次来到节点 b

　　2）此时 cur 在节点 b， cur 有左子树，找到其左子树的最右节点，即节点 d，d 的右指针指向 null ，让其指向 cur ，然后 cur 左移

　　　　此时二叉树结构如下， cur 第一次来到节点 d

　　3）此时 cur 在节点 d，cur 没有左子树， cur 右移

　　　　此时二叉树结构如下， cur 第二次来到节点 b

　　4）此时 cur 在节点 b， cur 有左子树，找到其左子树的最右节点，即节点 d，d 的右指针指向 cur ，让其指向 null ，然后 cur 右移

　　　　此时二叉树结构如下， cur 第一次来到节点 e

　　　　这里大家可能会有疑问：找  cur 的左子树的最右节点时，找到的不应该是节点 c 吗？

　　　　所以这里有细节要处理，找左子树最右节点的时候，遇到两种情况（右指针指向 null 或右指针指向 cur ）都需要停止寻找，用代码描述就是：

　　5）此时 cur 在节点 e， cur 有左子树，找到其左子树的最右节点，即节点 h，h 的右指针指向 null ，让其指向 cur ，然后 cur 左移

　　　　此时二叉树结构如下， cur 第一次来到节点 h

　　6）此时 cur 在节点 h， cur 没有左子树， cur 右移

　　　　此时二叉树结构如下， cur 第二次来到节点 e

　　7）此时 cur 在节点 e， cur 有左子树，找到其左子树的最右节点，即节点 h，h 的右指针指向 cur ，让其指向 null ，然后 cur 右移

　　　　此时二叉树结构如下， cur 第一次来到节点 k

　　8）此时 cur 在节点 k， cur 没有左子树， cur 右移

　　　　此时二叉树结构如下， cur 第二次来到节点 a（为什么是第二次？因为最初从 a 开始的）

　　9）此时 cur 在节点 a， cur 有左子树，找到其左子树的最右节点，即节点 k，k 的右指针指向 cur ，让其指向 null ，然后 cur 右移

　　　　此时二叉树结构如下， cur 第一次来到节点 c

　　10）此时 cur 在节点 c， cur 有左子树，找到其左子树的最右节点，即节点 g，g 的右指针指向 null ，让其指向 cur ，然后 cur 左移

　　　　此时二叉树结构如下， cur 第一次来到节点 f

　　11）此时 cur 在节点 f， cur 没有左子树， cur 右移

　　　　此时二叉树结构如下， cur 第一次来到节点 g

　　12）此时 cur 在节点 g， cur 没有左子树， cur 右移

　　　　此时二叉树结构如下， cur 第二次来到节点 c

　　13）此时 cur 在节点 c， cur 有左子树，找到其左子树的最右节点，即节点 g，g 的右指针指向 cur ，让其指向 null ， cur 右移

　　　　此时二叉树结构如下， cur = null

　　14）此时 cur 为 null ，遍历停止

　　　　可以看到，二叉树回到了最初的状态，最终结构与最初一致

　　前面步骤有点长，看的可能不够直观，我们来看个完整版的

　　上述的遍历就是 Morris Traversal ， cur 所经历的节点 a -> b -> d -> b -> e -> h -> e -> k -> a -> c -> f -> g -> c 组成了 Morris 序

　　在遍历的过程中，相信大家已经得出一个规律：有左子树的节点（b、e、a、c）会到达两次，没有左子树的节点（d、h、k、f、g）则只会到达一次

　　这绝对不是巧合啊！这是 Morris Traversal 移动规所产生的必然结果

　　对于那些能达到两次的节点，我们如何区分是第一次到达，还是第二次到达？

　　在上述的遍历过程中，相信大家已经找到答案了

　　　　1、如果其左子树的最右节点指向 null ，即 mostRight.right = null ，则该节点是第一次到达

　　　　2、如果其左子树的最右节点指向自身，即 mostRight.right = cur ，则该节点是第二次到达

　　经过了上述诸多的准备， Morris Traversal 代码实现就非常简单了

　　代码实现

　　相信大家都能看懂这个代码，没看懂的再去把前面的遍历过程再看看

Morris Traversal 一定要看懂，不然后面的深度遍历就玩不动了

先序遍历

　　我们对比下 先序序列 和 Morris 序列

　　发现了什么？ Morris Traversal 第二次到达的节点不打印，就是 先序序列 了

　　代码也就手到擒来了

中序遍历

　　我们对比下 中序序列 和 Morris 序列

　　只会遍历一次的节点，直接打印；会遍历两次的节点，第一次的时候不打印，第二次打印，就得到了 中序序列

　　代码很容易撸出来了

后序遍历

　　对比 后序序列 和 Morris 序列

　　一眼看不出有什么关系

　　通过 Morris Traversal 得到 后续序列 确实不容易想到，我们直接看前辈们的经验

　　被遍历到两次的节点的先后顺序：b、e、a、c

　　1、b 节点的左子树的右边界：d，逆序打印它还是 d

　　2、e 节点的左子树的右边界：h，逆序打印它还是 h

　　3、a 节点的左子树的右边界：b -> e -> k，逆序打印就是：k -> e -> b

　　4、c 节点的左子树的右边界：f -> g，逆序打印就是：g -> f

　　5、整棵树的右边界：a -> c，逆序打印就是：c -> a

　　把逆序列串起来：d -> h -> k -> e -> b -> g -> f -> c -> a，这就是 后序序列

　　问题又来了，如何逆序打印右边界，并且额外空间复杂度  O(1) ；其实就是单向链表的逆序输出，不知道的可以查看：单向链表的花式玩法 → 还在玩反转？

　　我们来看代码

总结

　　额外空间复杂度

　　只用到了有限几个变量， Morris Traversal 额外空间复杂度 O(1)

　　时间复杂度

Morris Traversal 时间复杂度是不是 O(N) ？

　　我们先看个极端的案例

　　它的时间复杂度是 2 * O(N)，这个没什么问题吧？

　　常数项可以拿掉，所以时间复杂度是 O(N)

　　注意点

Morris Traversal 遍历过程中会改变二叉树的结构，在一些并发的场景需要慎重使用

​