Morris算法-----二叉树遍历

一、算法介绍

　　Morris算法充分利用了二叉树叶子节点下的空间，从而可以在时间复杂度为O(N)，空间复杂度为O(1)的条件下，前中后序遍历二叉树(不是完全二叉树也可以使用)。

　　而常见的遍历二叉树的方法为递归和栈迭代，这两种方法的时间复杂度虽然也为O(N),但是空间复杂度需要O(N),因此Morris算法可以极大节省空间。

二、算法原理

　　首先来到当前节点记为cur。

　　1.如果cur无左孩子，cur向右移动。

　　2.如果cur有左孩子，那么找到cur左子树的最右的节点，记为mostRight。

　　　　2.1如果mostRight的right指针指向空，则让其指向cur，然后cur向左移动

　　　　2.2如果mostRight的right指针指向cur，让其指回空，然后cur向右移动。

三、算法实现

　　1.前序遍历

 1 public static void morrisPre(Node head) {
 2         if (head == null) {
 3             return;
 4         }
 5         Node cur = head;
 6         Node mostRight = null;
 7         while (cur != null) {
 8             mostRight = cur.left;
 9             if (mostRight != null) {//当cur有左孩子
10                 while (mostRight.right != null && mostRight.right != cur) {
11                     mostRight = mostRight.right;//找到左子树最右的孩子节点
12                 }
13                 if (mostRight.right == null) {//如果指向空则让其指向cur,cur左移
14                     mostRight.right = cur;
15                     System.out.print(cur.value + " ");
16                     cur = cur.left;
17                     continue;
18                 } else {
19                     mostRight.right = null;//否则让其指向空
20                 }
21             } else {
22                 System.out.print(cur.value + " ");
23             }
24             cur = cur.right;//右移
25         }
26         System.out.println();
27     }

　　2.中序遍历

 1     public static void morrisIn(Node head){
 2         if(head==null){
 3             return;
 4         }
 5         Node cur = head; //当前节点
 6         Node mostRight = null; //左子树的最右节点
 7         while(cur!=null){
 8             mostRight = cur.left;
 9             if(mostRight!=null){//当cur的有左孩子
10                 while(mostRight.right!=null&&mostRight.right!=cur){//找到左子树最右孩子
11                     mostRight = mostRight.right;
12                 }
13                 if(mostRight.right==null){//如果指向空则让其指向cur,cur左移
14                     mostRight.right = cur;
15                     cur = cur.left;
16                     continue;
17                 }else{
18                     mostRight.right=null;
19                 }
20             }
21             System.out.print(cur.value+" ");
22             cur = cur.right;
23         }
24         System.out.println();
25     }

　　3.后序遍历

　　前序遍历和中序遍历本质上并没有太大的区别，但Morris的后序遍历有较大的改动。

　　由于递归等版本的遍历二叉树后序遍历是在第三次到达节点的时候打印本次节点，但是Morris遍历只能到达一个节点两次。

　　因此可以采用到达该节点第二次的时候打印该节点左子树的逆序右边界的方法来打印后序遍历。

　　例如有一颗二叉树 4

　　　　　　　　　2　　　　6

　　　　　　1　　　　3　　5　　7

　　其中右边界分别为1 , 3 2 , 5 ， 7 6 4

　　其中要用到

　　反转链表

 1 public static Node reverseEdge(Node from){
 2         Node pre = null;
 3         Node next = null;
 4         while(from!=null){
 5             next = from.right;
 6             from.right = pre;
 7             pre = from;
 8             from = next;
 9         }
10         return pre;
11     }

　　打印边界函数

1 public static void printEdge(Node head){
2         Node tail = reverseEdge(head);
3         Node cur = tail;
4         while(cur!=null){
5             System.out.print(cur.value+" ");
6             cur = cur.right;
7         }
8         reverseEdge(tail);
9     }

　　后序遍历函数

 1     public static void morrisPos(Node head){
 2         if(head==null){
 3             return;
 4         }
 5         Node cur = head;
 6         Node mostRight = null;
 7         while(cur!=null){
 8             mostRight = cur.left;
 9             if(mostRight!=null){
10                 while(mostRight.right!=null&&mostRight.right!=cur){
11                     mostRight = mostRight.right;
12                 }
13                 if(mostRight.right==null){  //第一次到达
14                     mostRight.right = cur;
15                     cur = cur.left;
16                     continue;
17                 }else{  //第二次到达
18                     mostRight.right = null;
19                     printEdge(cur.left);
20                 }
21             }
22             cur = cur.right;
23         }
24         printEdge(head);//最后再单独打印最右边界
25         System.out.println();
26     }