Morris遍历
一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1)。通过利用原树中大量空闲指针的方式，达到节省空间的目的。
Morris遍历的关键
利用一棵树上大量的右指针空闲空间
Morris遍历细节
假设来到当前节点cur，开始时cur来到头节点位置
- 如果cur没有左孩子，cur向右移动(cur = cur.right)
如果cur有左孩子，找到左子树上最右的节点mostRight :
a. 如果mostRight的右指针指向空，让其指向cur，然后cur向左移动(cur = cur.left) b. 如果mostRight的右指针指向cur，让其指向null，然后cur向右移动(cur = cur.right)- cur为空时遍历停止
Morris遍历特点
任何结点只要有左树，都会来到两次，而且是在遍历完左树，第二次回到这个结点；如果某个结点没有左树，只会到一次。
Morris遍历的实质：利用左树上的最右结点的右指针状态，来标记到底是第一次还是第二次到的某个结点。如果某个结点（X）的左树上的最右结点的右指针指向空，说明肯定是第一次来到X结点。如果某个结点（X）的左树上的最右结点的右指针指向自己，说明是第二次来到X结点。总的来说，建立一种机制：对于没有左子树的节点只到达一次，对于有左子树的节点会到达两次，morris遍历时间复杂度依然是O(N)
通过Morris序加工出先序遍历
对于能回到自己两次的结点，在第一次到的时候就处理；对于只会到达一次的结点，就直接处理。
通过Morris序加工出中序遍历
对于能回到自己两次的结点，在第二次到的时候就处理；对于只会到达一次的结点，就直接处理。
问题：Morris遍历它每到一个结点，都会遍历该结点左树的右边界两次，那么它的时间复杂度真的还是O(N)吗？
所有左树的右边界都是不重的，也就是说，所有结点过它左树右边界的时间复杂度也就是整棵树的规模而已。
通过Morris序加工出后序遍历
在递归序中，后序遍历是第三次到达结点的时候，但是Morris遍历都无法回到一个结点三次，如何实现呢？答案是可以实现，并且时间复杂度依然是O(N)，额外空间复杂度O(1)。
把处理时机放在能回到自己两次的结点，并且是第二次回到自己的时候，但是不打印自己，而是逆序打印自己左树上的右边界。最后，Morris遍历完后，逆序打印整棵树的右边界。
难点在于如何逆序打印一棵树的右边界？不能用栈！！！
方法是链表反转！！！
笔试直接用递归，因为不看实现形式，只看做对了没有，笔试几乎只卡时间复杂度，不卡空间复杂度。
但是面试的时候，可以聊聊，因为在时间复杂度最优的情况下，还能省空间复杂度。
package com.harrison.class20;
/**
* @author Harrison
* @create 2022-03-31-13:09
* @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
*/
public class Code01_MorrisTraversal {
public static class Node {
public int value;
Node left;
Node right;
public Node(int data) {
this.value = data;
}
}
public static void morris(Node head){
if(head==null){
return ;
}
Node cur=head;
Node mostRight=null;
while(cur!=null){
mostRight=cur.left;
if(mostRight!=null){
while(mostRight.right!=null && mostRight.right!=cur){
mostRight=mostRight.right;
}
if(mostRight.right==null){
mostRight.right=cur;
cur=cur.left;
continue;
}else{// mostRight.right==cur
mostRight.right=null;
}
}
cur=cur.right;
}
}
public static void morrisPre(Node head){
if(head==null){
return ;
}
Node cur=head;
Node mostRight=null;
while(cur!=null){
mostRight=cur.left;
if(mostRight!=null){
while(mostRight.right!=null && mostRight.right!=cur){
mostRight=mostRight.right;
}
if(mostRight.right==null){
System.out.print(cur.value+" ");
mostRight.right=cur;
cur=cur.left;
continue;
}else{// mostRight.right==cur
mostRight.right=null;
}
}else{
System.out.print(cur.value+" ");
}
cur=cur.right;
}
System.out.println();
}
public static void morrisIn(Node head){
if(head==null){
return ;
}
Node cur=head;
Node mostRight=null;
while(cur!=null){
mostRight=cur.left;
if(mostRight!=null){
while(mostRight.right!=null && mostRight.right!=cur){
mostRight=mostRight.right;
}
if(mostRight.right==null){
mostRight.right=cur;
cur=cur.left;
continue;
}else{// mostRight.right==cur
mostRight.right=null;
}
}
System.out.print(cur.value+" ");
cur=cur.right;
}
System.out.println();
}
public static void morrisPos(Node head){
if(head==null){
return ;
}
Node cur=head;
Node mostRight=null;
while(cur!=null){
mostRight=cur.left;
if(mostRight!=null){
while(mostRight.right!=null && mostRight.right!=cur){
mostRight=mostRight.right;
}
if(mostRight.right==null){
mostRight.right=cur;
cur=cur.left;
continue;
}else{// mostRight.right==cur
mostRight.right=null;
printEdge(cur.left);
}
}
cur=cur.right;
}
printEdge(head);
System.out.println();
}
public static void printEdge(Node head){
Node tail=reverseEdge(head);
Node cur=tail;
while(cur!=null){
System.out.print(cur.value+" ");
cur=cur.right;
}
reverseEdge(tail);
}
public static Node reverseEdge(Node from){
Node pre=null;
Node next=null;
while(from!=null){
next=from.right;
from.right=pre;
pre=from;
from=next;
}
return pre;
}
public static void main(String[] args) {
Node head = new Node(4);
head.left = new Node(2);
head.right = new Node(6);
head.left.left = new Node(1);
head.left.right = new Node(3);
head.right.left = new Node(5);
head.right.right = new Node(7);
morris(head);
morrisPre(head);
morrisIn(head);
morrisPos(head);
}
}
