二叉树的Morris遍历

一、Morris 遍历

一般二叉树遍历都需要 O(h) 的空间来保存上一层的信息。而Morris 遍历利用叶子节点的左右孩子来存后序节点从而实现 O(1) 的空间复杂度。

1. Morris 遍历细节

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

(1) 如果cur.left == null，保存 cur 的值， cur 向右移动cur = cur.right

(2) 如果cur.left != null，找到左子树上最右的节点 mostRight:

a. 如果 mostRight 的右指针指向空mostRight.right == null，那么将mostRight.right = cur, 更新cur = cur.left

b.如果mostRight.right != null，说明之前已经访问过，第二次来到这里，表明当前子树遍历完成，保存 cur 的值，更新 cur = cur.right

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


public static void morris(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            cur = cur.right;
        } else {
            TreeNode mostRight = cur.left;
            while (mostRight.right != null && mostRight != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            } else {
                mostRight.right = null;
                cur = cur.right;
            }
        }
    }
}

二、先序遍历

只访问一次的节点，直接打印
访问两次的节点，第一次打印

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


public static void preorderTraversal(TreeNode root) {
    if (root == null) 
        return;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            // System.out.println(cur.val);
            cur = cur.right;
        } else {
            TreeNode mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                // System.out.println(cur.val);
                mostRight.right = cur;
                cur = cur.left;
            } else {
                cur = cur.right;
                mostRight.right = null;
            }
        }
    }
}

三、中序遍历

只访问一次的节点，直接打印
访问两次的节点，第二次打印

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


public static void preorderTraversal(TreeNode root) {
    if (root == null) 
        return;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            // System.out.println(cur.val);
            cur = cur.right;
        } else {
            TreeNode mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            } else {
                // System.out.println(cur.val);
                cur = cur.right;
                mostRight.right = null;
            }
        }
    }
}

四、后序遍历

访问两次的节点第二次访问时，逆序打印左树右边界
单独打印整棵树逆序的右边界

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


public static void printEdge(TreeNode head) {
    TreeNode tail = reverseList(head);
    TreeNode cur = tail;
    while (cur != null) {
        System.out.println(cur.val + " ");
        cur = cur.right;
    }
    reverseList(tail);
}

public static TreeNode reversList(TreeNode head) {
    if (head == null)
        return null;
    TreeNode pre = null;
    TreeNode cur = head;
    while (cur != null) {
        TreeNode temp = cur.right;
        cur.right = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

public static void preorderTraversal(TreeNode root) {
    if (root == null) 
        return;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            cur = cur.right;
        } else {
            TreeNode mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            } else {
                printEdge(cur.left);
                cur = cur.right;
                mostRight.right = null;
            }
        }
    }
    printEdge(root);
}