#import "../template.typ": *
#pagebreak()
= 二叉树 Morris 遍历

时间复杂度 O(n),空间复杂度 O(1)
通过利用袁术中大量空闲指针的方式,达到节省空间的目的

== 遍历细节

假设来到当前节点 cur,开始时 cur 在头节点

1. 若 cur 没有左孩子,cur 向右移动(`cur = cur.right`)
2. 若 cur 有左孩子,找到左子树上最右的节点 mostRight
  1. 若 mostRight 的右指针指向空,让其指向 cur,然后 cur 向左移动(`cur = cur.left`)
  2. 若 mostRight 的右指针指向 cur,让其指向 null,然后 cur 向右移动(`cur = cur.right`)
3. cur 为空时停止遍历

举例:

#image("./images/2022-03-30-18-06-16.png")

1->2->3->2->5->2->3->6->3->7

前序遍历:只经过一次的直接打印.二次经过的,打印第一次
中序遍历:只经过一次的直接打印.二次经过的,打印第二次
后序遍历:先逆序打印左树右边界,最后再逆序打印整个右边界.

when 递归套路?需要第三次信息(左树信息,右树信息,再整合)的强整合. when
Morris?没有第三次信息的强整合.

例如搜索二叉树.

时间复杂度分析: 左子树的右边界总代价最多 O(n)
