Morris遍历

二叉树递归遍历的实质是，只要这个节点不为空，那么这个节点一定会遍历3次，先序中序后续只不过是打印的时机不同。先序是第一次到达这个节点，中序是第二次，后序是第三次。Morris遍历高度模仿这个过程。Morris遍历，如果这个节点有左子树，那么能到达这个节点两次，没有左子树，只能到达这个节点一次。Morris遍历的时间复杂度为O(n)，空间复杂度为O(1)。

morris.jpg

Morris遍历的规则如下

• 来到的当前节点记为cur（引用）， 如果cur无左孩子，cur向右移动，cur = cur.right。

• 如果cur有左孩子，找到cur左子树最右的节点，记作mostRight

  1）如果mostRight的right指针指向空，让其指向cur，cur向左移动

  （cur = cur.left）。

  2）如果mostRight的right指针指向cur，让其指向空，cur向右移动。

然后，值得注意的是，Morris遍历可以写成二叉树的先中后，相关的方法会在代码中注释

public class MorrisTraversal {

    public static  class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int value){
            this.value = value;
        }
    }

    //morris遍历
    public 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 = null;
                }
            }
            System.out.print(cur.value + " ");
            cur = cur.right; //左孩子为空，直接向右移动
        }
        System.out.println();
    }

    //Morris前序遍历
    public 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){
                    mostRight.right = cur;
                    System.out.print(cur.value + " ");
                    cur = cur.left;
                    continue;
                }else {
                    mostRight.right = null;
                }
            }else {
                System.out.print(cur.value + " ");
            }
            
            cur = cur.right; //左孩子为空，直接向右移动
        }
        System.out.println();
    }


    
    //后面的太复杂了，暂时先放着。。。
    //Morris中序遍历


    //Morris后续遍历

    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);
        new MorrisTraversal().morris(head);
    }
}