引言

无论是递归遍历还是非递归遍历,我们都无法将空间复杂度达到O(1),因为对于之前的遍历来说,它们都是使用栈的(递归的是函数栈,而非递归的自己创建的栈),如果我们不使用栈能否实现遍历那,当然是可以的,这时候就要借助我们的叶子结点的空指针.这种遍历方式叫做Morris遍历.
Morris遍历就是借助指针的改变,从而实现能够从下层指向上层.
我来大概描述一下整个的过程,首先我们以中序遍历为例子,这是两个变量一个是cur1,另一个是cur2,循环的条件cur1!=null,cur2表示的是cur2的左子树,然后以cur2位基准,找到cur2中最右的结点,让这个结点,连向cur1.

图片.png

,然后我们一次执行这样的操作,使得最后的样子如下

图片.png
当我们走到cur2为空的时候,即这个时候我们走到了整个数的最左边,我们就可以开始遍历了,依次的通过right的指针运动.
在运动的过程中,但我们到达了原来的cur1,我们就要把指向变成null,我们来看一下
图片.png

然后我们来写一下大概的代码

Node cur1=head;
Node cur2=null;
while(cur1!=null)
{
     cur2=cur1.left;
     if(cur2!=null)//这个步骤是比不可少的
      {
            //循环,连接    
            //断开连接
      }
      cur1一直向right移动,然后打印
}

大概的思路就是上面那样,但是我们如果将连接和断开连接在同一个if中执行那,我们来看一下最终的代码

public static void morrisInOrder(Node head)
    {
        if(head!=null)
        {
            Node cur1=head;
            Node cur2=null;
            while(cur1!=null)
            {
                cur2=cur1.left;
                if(cur2!=null)
                {
                    while(cur2.right!=null&&cur2.right!=cur1)
                    {
                        cur2=cur2.right;
                    }
                    if(cur2.right==null)
                    {
                        cur2.right=cur1;
                        cur1=cur1.left;
                        continue;
                    }else
                    {
                        cur2.right=null;
                    }
                }
                System.out.print(cur1.value+" ");
                cur1=cur1.right;
            }
        }
    }

上面演示的是中序遍历,那么先序遍历和后序遍历我们要怎么样完成那,相对以之前的非递归的代码,我们这里的差异并不是很大,只需要稍微的修改一下打印的时机就可以了

图片.png
图片.png

所有综上所述,我们打印的时机为

• 建立连接时
• 当cur2为空时
  于是我们的代码也就出来了

public static void morrisPreOrder(Node head)
    {
        if(head!=null)
        {
            Node cur1=head;
            Node cur2=null;
            while(cur1!=null)
            {
                cur2=cur1.left;
                if(cur2!=null)
                {
                    while(cur2.right!=null&&cur2.right!=cur1)
                    {
                        cur2=cur2.right;
                    }
                    if(cur2.right==null)
                    {
                        cur2.right=cur1;
                        System.out.print(cur1.value+" ");
                        cur1=cur1.left;
                        continue;
                    }else
                    {
                        cur2.right=null;
                    }
                }else
                {
                    System.out.println(cur1.value+" ");
                }
                cur1=cur1.right;
            }
        }
    }

后序遍历打印的顺序如图

图片.png

所以这个时候打印的时机,就是在断开建立的连接的时候
而且需要时逆序

public static void printEdge(Node head)
    {
        Node tail=reverseEdge(head);
        Node cur=tail;
        while(cur!=null)
        {
            System.out.print(cur.value+" ");
            cur=cur.right;
        }
        reverseEdge(tail);
    }
    
    //相当于是链表的逆序
    public static Node reverseEdge(Node from)
    {
        Node pre=null;
        Node next=null;
        while(from!=null)
        {
            next=from.right;
            from.right=pre;
            pre=from;
            from=next;
        }
        return pre;
    }

然后在断开的时候打印
即printEdge(cur1.left);
不要忘了跳出循环时,要打印head开头的那个"链表"
代码如下

public static void morrisPos(Node head) {
        if (head == null) {
            return;
        }
        Node cur1 = head;
        Node cur2 = null;
        while (cur1 != null) {
            cur2 = cur1.left;
            if (cur2 != null) {
                while (cur2.right != null && cur2.right != cur1) {
                    cur2 = cur2.right;
                }
                if (cur2.right == null) {
                    cur2.right = cur1;
                    cur1 = cur1.left;
                    continue;
                } else {
                    cur2.right = null;
                    printEdge(cur1.left);
                }
            }
            cur1 = cur1.right;
        }
        printEdge(head);
        System.out.println();
    }

总结

这就是我们的进阶的遍历方式,空间复杂度为O(1),注意三种遍历方式的区别,就是打印的时机,我们需要注意一下后序的遍历,因为这里用到了链表的逆置