遍历二叉树的Morris序

参考书：《程序员代码面试指南》

这种方法的好处在于，它做到了时间复杂度为O(n)，额外空间复杂度为O(1)（只申请几个变量就可以完成整个二叉树的遍历）。

Morris遍历时cur访问节点的顺序就是morris序，可以在Morris序的基础上加工出前序遍历序列、中序遍历序列、后序遍历序列。
对于前序、中序，你只需要看要在Morris遍历过程中的合适位置加打印动作即可。
而对于后序，比较复杂。
下面举个例子，说明Morris遍历和对应的加工。


对于上图的二叉树来说，Morris序就是 cur访问过的顺序：1，2，4，2，5，1，3，6，3，7.
前序遍历序列就是第一次访问的顺序：1，2，4，5，3，6，7。
中序遍历序列就是第二次访问(附注：如果一个节点只被访问一次，那么第一次访问时直接打印)的顺序：4，2，5，1，6，3，7。
后序遍历序列是，每次恢复现场（恢复空闲指针）时，逆向打印cur的左子树的右边界；最后，逆序打印整个树的右边界，下面给出详细说明：
第一次恢复现场时，cur=②，逆向打印其左树的右边界：4；
第二次恢复现场时，cur=①，逆向打印其左树的右边界：5，2；
第三次恢复现场时，cur=③，逆向打印其左树的右边界：6；
最后，逆序打印整个树的右边界：7，3，1；
所以，整个后序遍历序列是 4，5，2，6，7，3，1.

public class Morris {

    public void morris(TreeNode head){// morris遍历
        TreeNode cur=head;
        TreeNode rightMost=null;
        while (cur!=null){
            rightMost=cur.left;
            if(rightMost!=null){
                while (rightMost.right!=null&&rightMost.right!=cur){
                    rightMost=rightMost.right;

                }

                if(rightMost.right==null){
                    rightMost.right=cur;
                    cur=cur.left;
                    continue;
                }

                if(rightMost.right==cur){
                    rightMost.right=null;
                    cur=cur.right;
                    continue;
                }
            }else {
                cur=cur.right;
            }

        }


    }

    public static void morrisPreTraversal(TreeNode head){
        TreeNode cur=head;
        TreeNode rightMost=null;
        while (cur!=null){
            rightMost=cur.left;
            if(rightMost!=null){
                while (rightMost.right!=null&&rightMost.right!=cur){
                    rightMost=rightMost.right;

                }

                if(rightMost.right==null){
                    rightMost.right=cur;
                    System.out.println(cur.value);
                    cur=cur.left;
                    continue;
                }

                if(rightMost.right==cur){
                    rightMost.right=null;
                    cur=cur.right;
                    continue;
                }
            }else {
                System.out.println(cur.value);
                cur=cur.right;
            }

        }
    }

    public static void morrisInTraversal(TreeNode head){
        TreeNode cur=head;
        TreeNode rightMost=null;
        while (cur!=null){
            rightMost=cur.left;
            if(rightMost!=null){
                while (rightMost.right!=null&&rightMost.right!=cur){
                    rightMost=rightMost.right;

                }

                if(rightMost.right==null){
                    rightMost.right=cur;

                    cur=cur.left;
                    continue;
                }

                if(rightMost.right==cur){
                    rightMost.right=null;
                    System.out.println(cur.value);
                    cur=cur.right;
                    continue;
                }
            }else {
                System.out.println(cur.value);
                cur=cur.right;
            }

        }
    }

    public static void morrisPostTraversal(TreeNode head){
        TreeNode cur=head;
        TreeNode rightMost=null;
        while (cur!=null){
            rightMost=cur.left;
            if(rightMost!=null){
                while (rightMost.right!=null&&rightMost.right!=cur){
                    rightMost=rightMost.right;

                }

                if(rightMost.right==null){
                    rightMost.right=cur;

                    cur=cur.left;
                    continue;
                }

                if(rightMost.right==cur){
                    rightMost.right=null;
                    printReverseRB(cur.left);
                    cur=cur.right;
                    continue;
                }
            }else {

                cur=cur.right;
            }

        }
        printReverseRB(head);
    }

    private static void printReverseRB(TreeNode head) {
        TreeNode next=null;
        TreeNode cur=head;
        TreeNode pre=null;

        pre=reverseEdge(cur);
        cur=pre;
        while (cur!=null){
            System.out.println(cur.value);
            cur=cur.right;
        }
        // restore
        reverseEdge(pre);
    }
    private static TreeNode reverseEdge(TreeNode head){
        TreeNode next=null;
        TreeNode cur=head;
        TreeNode pre=null;
        while (cur!=null){
            next=cur.right;
            cur.right=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }

    public static void main(String[] args) {
        TreeNode head=new TreeNode(1);
        head.left=new TreeNode(2);
        head.right=new TreeNode(3);
        head.left.left=new TreeNode(4);
        head.left.right=new TreeNode(5);
        head.right.left=new TreeNode(6);
        head.right.right=new TreeNode(7);

        morrisPreTraversal(head);
        System.out.println();
        morrisInTraversal(head);
        System.out.println();
        morrisPostTraversal(head);

    }



}

class TreeNode{
    TreeNode right;
    TreeNode left;
    int value;
    public TreeNode(int val){
        this.value=val;
        this.right=null;
        this.left=null;
    }
}