遍历二叉树的Morris序

发布时间:2023年12月24日

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

这种方法的好处在于,它做到了时间复杂度为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;
    }
}


文章来源:https://blog.csdn.net/qq_43448491/article/details/135179570
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。