神迹！开启遍历新时代 —— 神级遍历Morris算法，时间复杂度O(n)，空间复杂度O(1)

た入场券 2023-02-17 02:20 26阅读 0赞

### 一、递归方式和非递归方式遍历 ###

二叉树节点数据结构

public static class Node {
            public Integer value;
            public Node left;
            public Node right;
            public Node(Integer value){
                this.value = value;
            }
        }

递归的方式遍历二叉树算法。

public void process(Node head){
            if(head == null){
                return ;
            }
            //1、先序遍历
            process(head.left);
            //2、中序遍历
            process(head.right);
            //3、后序遍历
        }

这是我们平时写的递归方式遍历节点，只要在对应的1、2、3位置插入输出语句就变成了一个先序、中序、后序遍历。

实际上也是隐含了这样一个意思：**只要二叉树节点不为null，那么这个在当前节点的这个函数就会被访问三次。**

这种递归方式的时间复杂度是O（n），那么有的小伙伴可能说这个节点的函数不是被访问了三次吗，我们平时说的在常数倍数的O（n），实际上就是O（n）这个时间复杂度。这个方法的空间复杂度度是O（n），这个时间复杂度不是体现在变量上面，而是递归，jvm内存栈的堆积。

而非递归方式，举一个栗子，先序遍历。

public static void preOrder(Node head){
        if(head == null){
            return ;
        }
        Stack<Node> stack = new Stack<>();
        while(!stack.isEmpty() || head != null){
            if(head != null){
                System.out.println(head.value);
                stack.push(head);
                head = head.left;
            }else{
                Node temp = stack.pop();
                head = temp.right;
            }
        }
    }

同样用了栈这个结构，所以空间复杂度是O（n）。实际上时间复杂度已经到了不可优化，但是空间复杂度是否可以继续优化呢？答案是肯定的，这个就是我们要说的神级遍历Morris算法。空间复杂度O（1），这个指标也就是说，我不利用额外栈这些的辅助空间，我只在二叉树上面就能完成先、中、后序遍历。

### 二、Morris算法 ###

morris主要利用了二叉树的那些null节点

先说一下morris算法的规则，然后画图举例，最后讲算法code。

规则：

（1）判断节点是否有左孩子，如果没有直接进入左孩子即cur = cur.right。否则进入（2）

（2）如果节点含有左子树，找到该左孩子的右子树上面最右节点mostRight，如果mostRight.right为null，那么进入（3），否则进入4

（3）如果mostRight.right = null，那么设置该mostRight.right = cur，指向当前节点。当前节点向左移动，cur = cur.left。

（3）如果mostRight.right != null，那么设置mostRight.right = null，当前节点向右移动cur = cur.right。

以这个为例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1][]

当前cur = 1，左子树存在，找到mostRight = 5，mostRight.right = null，所以符合（3）cur = cur.left，当前节点来到2，然后5的右孩子指向1，则如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 3][]

同理符合（3）：cur来到4位置，如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 4][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 5][]

这个时候，符合（1），cur直接通过4右节点到2。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 6][]![20200610210049778.png][]

当前情况，mostRight = 4,mostRight.right = cur，不等于null，符合条件（4）如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 7][]![20200610210107616.png][]

这个情况符合情况（1），那么直接回退到1。如图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 8][]![20200610210128322.png][]

符合（4），如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 9][]![20200610210146570.png][]

符合（3）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 10][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 11][]

符合（1）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 12][]![20200610210224982.png][]

符合（4）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 13][]![20200610210244550.png][]

遍历结束！！

我们可以发现一个规律就是，**有的节点被访问了两次，而这些节点都是有左孩子的，没有左孩子的节点只被访问了一次。这个对于我们之后的先序、中序、后序遍历至关重要！！！**

然后我们上代码：

public static void morrisIn(Node head) {
            if (head == null) {
                return;
            }
            Node cur = head;
            Node mostRight = null;
            while(cur != null){
                mostRight = cur.left;
                //规则（2）查看左子树是否是null，如果不等于null
                if(mostRight != null){
                    //找到左子树最右节点
                    while(mostRight.right != null && mostRight.right != cur){
                        mostRight = mostRight.right;
                    }
                    //规则（3）如果等于null，指向当前节点，当前节点左移动
                    if(mostRight.right == null){
                        mostRight.right = cur;
                        cur = cur.left;
                        continue;
                    }else{
                    //规则（4）如果指向当前节点，那么就指向null，然后跳到右子树
                        mostRight.right = null;
                    }
                }
                //规则（1）等于null，直接到右子树
                cur = cur.right;
            }
        }

这个代码就是严格按照规则走的morris遍历。先不要去管什么先序、后序、中序。那个很简单都是基于这个规则来的。先看懂遍历的代码，就像看递归的那个似的，看清楚执行的本身，自然而然就知道了如何去搞。

### 三、用morris实现先序、中序、后序遍历 ###

（1）先序遍历：我们之前提到过，如果一个节点有左子树，那么它会被访问两次，如果一个节点没有左子树，就只会被访问一次。所以呢，我们在第一次到达节点的时候输出语句对应的值，就是先序遍历！

如何判断是第一次到达节点呢，规则（3）那么就是mostRight = null的时候，这个时候遍历就是第一次，因为第二次的时候会指向当前的节点。对于规则（1），只有一次到达的机会，那么就直接访问就可以了，下面的代码就是添加了一个else和输出。

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 = null;
                    }
                }else{
                    System.out.print(cur.value + " ");
                }
                cur = cur.right;
            }
            System.out.println();
        }

（2）中序遍历：就是在有左孩子的节点第二次回退到该节点的时候才输出，对于没有左孩子的节点，访问的时候直接打印。

public static void morrisIn(Node head) {
                if (head == null) {
                    return;
                }
                Node cur = head;
                Node mostRight = null;
                while(cur != null){
                    mostRight = cur.left;
                    //规则（2）查看左子树是否是null，如果不等于null
                    if(mostRight != null){
                        //找到左子树最右节点
                        while(mostRight.right != null && mostRight.right != cur){
                            mostRight = mostRight.right;
                        }
                        //规则（3）如果等于null，指向当前节点，当前节点左移动
                        if(mostRight.right == null){
                            mostRight.right = cur;
                            cur = cur.left;
                            continue;
                        }else{
                            //规则（4）如果指向当前节点，那么就指向null，然后跳到右子树
                            mostRight.right = null;
                        }
                    }
                    System.out.print(cur.value + " ");
                    //规则（1）等于null，直接到右子树
                    cur = cur.right;
                }
                System.out.println();
        }

对于先序和中序还好，跟递归的过程差不多，他们输出的时机还是跟递归先序和中序的时机是一样的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 14][]

在Morris发表论文的时候，只有先序和中序，后序是后来的大佬们在morris基础上研究得出的。

后序遍历实际上采用了一个技巧：

**只关注能够来到两次的节点，逆序打印左子树右边界，然后单独逆序打印整棵树的右边界。**

public static void morrisPost(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;
                        printEdge(cur.left);
                    }
                }
                cur = cur.right;
            }
            printEdge(head);
            System.out.println();
        }
    
        //逆序打印
        private static void printEdge(Node head) {
            Node pre = tranfer(head);
            printInfo(pre);
            tranfer(pre);
        }
        //打印
        private static void printInfo(Node head){
            Node next = head;
            while(next != null){
                System.out.print(next.value + " ");
                next = next.right;
            }
        }
        
        //逆序
        private static Node tranfer(Node node){
            Node pre = null;
            Node curl = node;
            while(curl != null){
                Node next = curl.right;
                curl.right = pre;
                pre = curl;
                curl = next;
            }
            return pre;
        }

### 四、分析一下时间复杂度为什么是O（n） ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 15][]

以这个为例子！

当到达1节点的时候，我们需要遍历2、5、11，找到mostRight。

当到达2节点的时候，我们需要遍历4，9，找到mostRight。

当到达4节点的时候，我们需要遍历8，找到mostRight。

当到达5节点的时候，我们需要遍历10，找到mostRight。

当回退到4的时候，需要遍历8。

当回退到5的时候，需要遍历10

当回退到2的时候，需要遍历4，9。

当回退到1的时候，需要遍历2，5，11。

当遍历到3的时候，我们需要遍历6、13。

当遍历到6的时候，我们需要遍历12。

当回退到6的时候，需要遍历12。

当回退到3的时候，需要遍历6、13。

当遍历到7的时候，我们需要遍历14。

当回退到7的时候，需要遍历14。

当遍历到15的时候结束。

可以看到，我们的整个遍历过程中，访问每一个节点的次数都是在常数时间内的！所以是O（n）。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200610205104940.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200610205954780.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200610205142947.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200610210016786.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200610205225682.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200610210034574.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200610205335823.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[20200610210049778.png]: https://img-blog.csdnimg.cn/20200610210049778.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200610205501923.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[20200610210107616.png]: https://img-blog.csdnimg.cn/20200610210107616.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200610205615267.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[20200610210128322.png]: https://img-blog.csdnimg.cn/20200610210128322.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200610205700263.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[20200610210146570.png]: https://img-blog.csdnimg.cn/20200610210146570.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200610205736744.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/2020061021020436.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200610205825163.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[20200610210224982.png]: https://img-blog.csdnimg.cn/20200610210224982.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20200610205858564.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[20200610210244550.png]: https://img-blog.csdnimg.cn/20200610210244550.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20200610213107875.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20200610225357649.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70