Morris遍历

Morris遍历

一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1)。

通过利用原树中大量空闲指针的方式，达到节省空间的目的。

Morris遍历的关键

利用一棵树上大量的右指针空闲空间

Morris遍历细节

假设来到当前节点cur，开始时cur来到头节点位置

1. 如果cur没有左孩子，cur向右移动(cur = cur.right)

2. 如果cur有左孩子，找到左子树上最右的节点mostRight :
   a. 如果mostRight的右指针指向空，让其指向cur，然后cur向左移动(cur = cur.left)
   b. 如果mostRight的右指针指向cur，让其指向null，然后cur向右移动(cur = cur.right)

3. 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);

    }
}