Morris遍历

mathor

发布于 2018-08-17 15:37:27

3650

发布于 2018-08-17 15:37:27

文章被收录于专栏：mathor

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

如果cur无左孩子(cur.left == null)，cur向右移动（cur = cur.right）
如果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();
}