Morris traversal

Morris Traverse

A way to traverse a binary tree , And the time complexity O(N), Extra space complexity O(1). By using a large number of free pointers in the original tree , Achieve the purpose of saving space .

Morris The key of traversal

Use a large amount of free space of the right pointer on a tree

Morris Traverse the details

Suppose you come to the current node cur, At the beginning of the cur Come to the head node

1. If cur There is no left child ,cur To the right (cur = cur.right)

2. If cur There are left children , Find the rightmost node on the left subtree mostRight :
   a. If mostRight The right pointer of points to null , Make it point cur, then cur Move to the left (cur = cur.left)
   b. If mostRight The right pointer of points to cur, Make it point null, then cur To the right (cur = cur.right)

3. cur When null, traversal stops

Morris Traversal characteristics

As long as any node has a left tree , Will come twice , And after traversing the left tree , Return to this node for the second time ; If a node has no left tree , Only once .

Morris The essence of traversal

Using the right pointer state of the rightmost node on the left tree , To mark whether it is the first time or the second time to a node . If a node （X） The right pointer of the rightmost node on the left tree of points to null , It must be the first time to come to X node . If a node （X） The right pointer of the rightmost node on the left tree of points to itself , It's the second time you come to X node . in general , Establish a mechanism ： For nodes without left subtree, they arrive only once , For a node with a left subtree, it will arrive twice ,morris The traversal time complexity is still O(N)

Recursive method , You can also know whether it is your first time , Because the system stack will keep all intermediate information ; The way the stack records information , Of course, I know how many times I came to myself . Again , When I went to the left tree , When I go back to myself , I also know that it is the second time to come to me , Because the system stack will retain all process information . therefore Morris Traversal is essentially using the right pointer of the rightmost node on the left tree of any node , Pay tribute to recursive behavior ！！！

Digression

Morris What's the use of traversal ？ The lower level of things is not required to be more efficient , It requires more space , If the system uses more space , There is less space left for user applications ！

adopt Morris Sequence processing out of the first sequence traversal

For the node that can return to oneself twice , Deal with it the first time you arrive ; For nodes that will arrive only once , Just deal with it directly .

adopt Morris The middle order traversal is processed in order

For the node that can return to oneself twice , Deal with it the second time you arrive ; For nodes that will arrive only once , Just deal with it directly .

problem ：Morris Traverse it to every node , Will traverse the right boundary of the left tree of the node twice , So its time complexity is really O(N) Do you ？

The right boundary of all left trees is not heavy , in other words , The time complexity of all nodes passing through its left and right boundaries is just the size of the whole tree .

adopt Morris After the sequence processing, the sequence traversal

In recursive order , Post order traversal is the third time to reach the node , however Morris Traversal cannot return to a node three times , How to achieve it ？ The answer is that , And the time complexity is still O(N), Extra space complexity O(1).

Put the processing time at the node where you can return to yourself twice , And the second time I came back to myself , But don't print yourself , Instead, print the right boundary on your left tree in reverse order . Last ,Morris After traversing , Print the right boundary of the whole tree in reverse order .


The difficulty of printing a right boundary tree is how to reverse the order ？ You can't use the stack ！！！

The method is to reverse the linked list ！！！

The written test uses recursion directly , Because we don't look at the implementation form , Just see it as right... No , The written examination is almost only limited to time complexity , No card space complexity .

But during the interview , We can talk about , Because when the time complexity is optimal , It also saves space complexity .

package com.harrison.class20;

/** * @author Harrison * @create 2022-03-31-13:09 * @motto  looking for him for thousand times in the crowd , Suddenly look back , The man was in the dim light . */
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);

    }
}