MENU

Morris遍历

August 13, 2018 • Read: 141 • 算法

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

暂无

最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code