Morris 遍历

Morris 算法遍历一棵二叉树，时间复杂度 O (n)，但是空间复杂度却只用神奇的 O (1)，下面说一下 Morris 遍历的流程，首先规定来到的当前结点即为 cur

1. 如果 cur 无左孩子 (cur.left = null)，cur 向右移动（cur = cur.right）

2. 如果 cur 有左孩子 (cur.left != null)，找到 cur 左子树上最右的结点，记为 mostRight

   1. 如果 mostRight 无右孩子 (mostRigt.rigth = null)，则让其指向 cur (mostRight = cur)，同时 cur 向左移动 (cur = cur.left)
   2. 如果 mostRight 的右孩子指向 cur，则让其指向 null (mostRight.right = null)，同时 cur 向右移动 (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 == null) {
                mostRight.right = cur;
                System.out.println(cur.value + " ");
                cur = cur.left;
                continue;
            } else
                mostRight.right = null;
        }
        cur = cur.right;
    }
    System.out.println();
}

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

后序 Morris展开目录

暂无