Morris遍历二叉树

时间复杂度：O（N）
空间复杂度：O（1）

具体流程：
假设当前来到的节点记为cur

• 如果cur无左孩子，cur向右移动（cur=cur.right）
• 如果cur有左孩子，找到cur左子树的最右节点，记为mostright：
  1. 如果mostright的右指针指向空，让其指向cur，cur向左移动（cur=cur.left）
  2. 如果mostright的右指针指向cur，让其指向空，cur向右移动（cur=cur.right）

中序遍历，在最后一次到达该节点时打印

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 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 = cur
                mostRight.right = null;
            }
        } else {
            System.out.print(cur.value + " "); // 第一次来到这个节点
        }
        cur = cur.right;
    }
    System.out.println();
}

后序遍历：只关注能到达2次的节点，在第二次到达该节点时，逆序打印左子树右边界。最后打印整棵树的右边界。
逆序打印实现：类似反转链表打印后再恢复原样