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序加工出先序遍历

对于能回到自己两次的结点，在第一次到的时候就处理；对于只会到达一次的结点，就直接处理。

通过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);

    }
}