Morris遍历

写在前面

笔试不推荐用，容易出错，平常写就好

面试推荐用，增加印象分

综述

一种遍历二叉树的方式，并且时间复杂度是O(N), 额外空间复杂度是O(1)

通过利用原树中大量空闲指针的方式，达到节省空间的目的。

Morris遍历细节

假设来到当前节点cur,开始时cur来到头结点位置

1. 如果cur没有左孩子，cur向右移动(cur = cur.right)

2. 如果cur有左孩子，找到左子树上最右的节点mostRight:

   a. 如果mostRight的右指针指向空， 让其指向cur, 然后cur向左移动(cur = cur.left)

   b. 如果mostRight的右指针指向cur， 让其指向null, 然后cur向右移动(cur = cur.right)

3. cur为空时遍历停止

Morris遍历图解

///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////

等等

cur依次出现的顺序是：1 2 4 2 5 1 3 6 3 7

相关分析

每一个有左子树的节点都会出现两次， 比如 1 2 3

如果一个结点有左树，怎样判断是第几次回到自己

答：通过自己左子树的最右节点指向谁来确定，如果指向null,就是第一次，如果指向自己就是第二次。

相关代码

    //定义结点结构
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static void morris(Node head){
        if (head == null){
            return;
        }
        //当前cur先来到head节点
        Node cur = head;
        //承载是否有左子树和有左子树的情况下左子树最右侧的节点
        Node mostRight = null;
        while(cur != null){//符合上面morris的流程，直到cur是null才停止
            mostRight = cur.left;//mostRight是cur左孩子
            if (mostRight != null){//有左子树
                //右侧不为空就进行下去，如果右侧不是当前节点进行下去，符合上面morris的流程
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                //如果当前节点左子树最右侧节点的右侧是null
                if (mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else {
                    //如果当前节点左子树最右侧节点的右侧是cur
                    mostRight.right = null;
                }
            }
            cur = cur.right;
        }
    }
复制代码

复杂度分析

每来到一个节点就会遍历一下它的左孩子的右边界，这个会不会使时间复杂度上升呢？

答：因为每个需要遍历右边界的节点，遍历的节点都是不同的，所以时间复杂度不会变化是O(N)。

【图片】

空间复杂度是O(1)。