前置说明
不了解二叉树非递归遍历的可以看我之前的文章【数据结构与算法】二叉树模板及例题
Morris 遍历
概述
Morris 遍历是一种遍历二叉树的方式,并且时间复杂度O(N),额外空间复杂度O(1) 。通过利用原树中大量空闲指针的方式,达到节省空间的目的
分析
设一棵二叉树有 n 个节点,则所有节点的指针域总和为 2 * n ,所有节点的非空指针域总和为 n - 1(非根节点被一个指针指向,根节点不被指针指向),所有节点的空指针域总和为 2n - (n - 1) = n + 1。
可以看到有大量的空指针域没有用到,在可以改变原二叉树结构的前提下,我们可以通过合理利用节点的空指针域,不开辟额外空间进行二叉树的非递归遍历。
❓ 那么先序、中序、后序遍历的节点访问顺序是如何确定的呢
如上图,根据紫色箭头顺序访问,第一次访问到的节点组成的集合就是先序遍历的结果。类似的,第二次访问到的节点组成的集合就是中序遍历的结果;第三次访问到的节点组成的集合就是后序遍历的结果。
通过设置节点访问不同次数的操作就可以实现三种遍历。
❓ Morris 遍历的实质:建立一种机制,对于没有左子树的节点只到达一次,对于有左子树的节点会到达两次