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

2023年6月7日下午7:17 • 数据结构和算法 • 阅读 156

开心一刻

一天，有个粉丝遇到感情方面的问题，找我出出主意

粉丝：我女朋友吧，就是先天有点病，听不到人说话，也说不了话，现在我家里人又给我介绍了一个，我该怎么办

我：这个问题很难去解释，我觉得一个人活着，他要对身边的人负责，对家人负责，对自己负责

从语音中我能感受得到粉丝很难受，我继续补充

我：我不是说让你放弃掉你的女朋友，你们一定是有一定的感情基础才在一起的，但你还是需要衡量衡量你的未来

我能明显感觉到粉丝已经在抽泣，继续说道

我：当然，这个时候离开肯定是不合适的，对吧？

粉丝：是的

我：这种感情的问题，我很难说让你怎么样，这个只有你自己去衡量，找到一个最合适的解决办法

粉丝哭泣到：我真的不知道怎么办

我最不忍心看别人哭，安慰道：你先别哭，问题总有办法解决的，哭不是解决问题的办法，你先平复下

过了一会，粉丝说道：我知道了，我还是遵从家里的意见吧，给我现在的女朋友气放了

我：女朋友气… 我放你个大乌龟

额外空间复杂度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) ；其实就是单向链表的逆序输出，不知道的可以查看：单向链表的花式玩法 → 还在玩反转？

我们来看代码

总结