遍历二叉树的神级方法--Morris 遍历

Morris 遍历可以做到O(N)的时间复杂度，O(1)的空间复杂度

有以下几个点先要了解

1. 遍历的时候因为没有指向父节点的指针，无法从下往上走，所以采用栈，但是树的节点有很多的left，right指向null，Morris利用了这些指针

2. 遍历树过程中：第一次遇到某个节点就输出是前序遍历，第二次遇到再输出是中序遍历，第三次遇到再输出是后续遍历

3种遍历的历程都是一样的，区别在于打印的时机不同，先看历程：

拿到一个节点N，判断它的左子树的最右节点的右孩子指向null还是N，如果没有左子树直接往右移动

（1）指向null：依次要左子树每个节点X的前驱都指向X自己

（2）指向N：把前驱节点右指针指向null（复原之前的树结构），往右移动（这里因为可能已经修改了右孩子的指向，所以右移要么是往右子树移动，要么往上移动，从X的前驱移动到X）

那打印顺序呢？

（1）在往右移动之前打印——中序（因为是第二次遇到该节点）

（2）当节点的前驱指向null，或者左子树节点为null打印该节点——先序（因为是第1次遇到该节点，或者此时不打印后面就没有机会遍历到了）

（3）当发现前驱节点指向自己（即下图的情况），逆序打印左子树的右边界，最后在打印root的右边界——后序

为什么这样逆序打印右边界就可以输出后序呢？因为树可以看成一系列的右边界组成，而后续遍历与右边界的关系比较清晰，（仔细想想！）

那怎么O(1)逆序呢？类似于链表逆序打印，打印完了再逆序回来

可以证明时间复杂度O(N)

不过这TM谁遍历用这个，即使看过也记不住，虽然记住了可以在面试官目前装逼