二叉树morris遍历，空间复杂度为 O(1)

二叉树递归遍历如下：

额外空间复杂度为：树的高度。原因：自己虽然没有申请额外空间，但是递归过程是要压栈占用栈内存的，栈帧数最大就为树的高度

// 每个节点只到1或2次(有限次)，时间复杂度为O(N)
public static void process(Node root) {
    if (root == null) return;
    // 1.此处输出当前节点的值——前序
    process(root.left);
    // 2.此处输出当前节点的值——中序
    process(root.right);
    // 3.此处输出当前节点的值——后序
}

Morris遍历细节

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

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

2. 如果cur有左孩子，就看左子树上最右的节点mostRight（如果左子树没有右节点，就是它自己）:

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

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

3. cur为空时遍历停止

Morris序：任何节点有左树则到两次，没左数则到一次

对于到两次的，如何确定是第一次还是第二次到？如果左子树最右节点没有指向cur，则说明是第一次到

morris遍历

public static void morris(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;
            }
        }
        cur = cur.right;
    }
}

morris先序遍历

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) {
                System.out.print(cur.val + " ");  // 如果有左子树，则第一次来就打印
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else {
                mostRight.right = null;
            }
        } else { //没有左子树，只来一次，直接打印
            System.out.print(cur.val + " ");
        }
        cur = cur.right;
    }
}

morris中序遍历

public static void morrisIn(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 {
                System.out.print(cur.val + " "); // 如果没有左子树，则第二次到的时候打印
                mostRight.right = null;
            }
        } else { //没有左子树，只来一次，直接打印
            System.out.print(cur.val + " ");
        }
        cur = cur.right;
    }
}

morris后序遍历

public static void morrisPos(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);
}
 
// 逆序打印右边界
public static void printEdge(Node head) {
    Node tail = reverseEdge(head);
    Node cur = tail;
    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.right;
    }
    reverseEdge(tail);
}
 
// 其实跟反转链表一样的道理
public static Node reverseEdge(Node head) {
    Node pre = null;
    Node next = null;
    while (head != null) {
        next = head.right;
        head.right = pre;
        pre = head;
        head = next;
    }
    return pre;
}

morris 遍历的优缺点

优点：相比于递归遍历优化了空间复杂度，由O(logN)  到了 O(1)

缺点：代码相对复杂一点点，并且虽然时间复杂度同样为 O(N)，但它的整体过程较麻烦，跑起来是相对于递归来说还是慢一些的