【数据结构与算法】二叉树的 Morris 遍历（前序、中序、后序）

前置说明

不了解二叉树非递归遍历的可以看我之前的文章【数据结构与算法】二叉树模板及例题

Morris 遍历

概述

Morris 遍历是一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1) 。通过利用原树中大量空闲指针的方式，达到节省空间的目的

分析

设一棵二叉树有 n 个节点，则所有节点的指针域总和为 2 * n ，所有节点的非空指针域总和为 n - 1（非根节点被一个指针指向，根节点不被指针指向），所有节点的空指针域总和为 2n - (n - 1) = n + 1。

可以看到有大量的空指针域没有用到，在可以改变原二叉树结构的前提下，我们可以通过合理利用节点的空指针域，不开辟额外空间进行二叉树的非递归遍历。

❓ 那么先序、中序、后序遍历的节点访问顺序是如何确定的呢

如上图，根据紫色箭头顺序访问，第一次访问到的节点组成的集合就是先序遍历的结果。类似的，第二次访问到的节点组成的集合就是中序遍历的结果；第三次访问到的节点组成的集合就是后序遍历的结果。

通过设置节点访问不同次数的操作就可以实现三种遍历。

❓ Morris 遍历的实质：建立一种机制，对于没有左子树的节点只到达一次，对于有左子树的节点会到达两次