通常，实现二叉树的前序（preorder）、中序（inorder）、后序（postorder）遍历的迭代版本都需要 O(n) 的空间复杂度，那么有没有可能使用 O(1) 空间进行迭代遍历呢？答案是肯定的。
本文将介绍 Morris Traversal 遍历二叉树的方法，该算法能够做到 O(1) 空间复杂度的迭代遍历，并在遍历完成后二叉树依然保持原始状态（遍历过程中可能被修改）。
Morris Traversal
要使用 O(1) 空间进行遍历，最大的难点在于，遍历到子节点的时候怎样重新返回到父节点（假设节点中没有指向父节点的 p 指针），由于不能用栈作为辅助空间。为了解决这个问题，Morris 方法用到了线索二叉树（threaded binary tree）的概念。在 Morris 方法中不需要为每个节点额外分配指针指向其前驱（predecessor）和后继节点（successor），只需要利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点就可以了。
树结点定义
1
2
3
4
5
6
7
8
9
10
11
| public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {}
public TreeNode(int x) {
val = x;
}
}
|
中序遍历
- 1.设当前结点为cur
- 2.如果当前结点的左孩子为空，则输出当前结点并将其右孩子作为当前结点。
- 3.如果当前结点的左孩子不为空，则找出左子树的最右结点，记为pre。
- 如果pre.right为空，则将pre.right指向当前结点，然后当前结点更新 为当前结点的左孩子。
- 如果pre.right指向当前结点，则将pre.right重新设为空（恢复树的形状）， 输出当前结点，然后当前结点更新为当前结点的右孩子。
- 4.重复步骤2、3，直到当前结点为空。
下图为每一步迭代的结果（从左至右，从上到下），cur代表当前节点，深色节点表示该节点已输出。
参考实现：
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
49
50
51
52
53
54
55
56
57
58
| package learn.binarytree.traverse;
import common.TreeNode;
import common.TreePrinter;
public class MorrisInorderTraversal {
public void inorder(TreeNode root) {
TreeNode cur = root, pre;
while (cur != null) {
if (cur.left == null) {
System.out.print(cur.val + " ");
cur = cur.right;
} else {
pre = cur.left;
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = cur;
cur = cur.left;
} else {
pre.right = null;
System.out.print(cur.val + " ");
cur = cur.right;
}
}
}
}
public static void main(String[] args) {
int[] pre = new int[]{6, 2, 1, 4, 3, 5, 7, 9, 8};
int[] in = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
TreeNode root = TreeNode.buildFromPreAndIn(pre, in);
TreePrinter.prtHorizontalStyle(root);
new MorrisInorderTraversal().inorder(root);
}
}
|
复杂度分析：
寻找左子树最右结点（也即当前结点的前驱）的时间复杂度为 O(n)，n 个节点的二叉树中一共有 n-1 条边，整个过程中每条边最多只走 2 次，一次是为了定位到某个节点，另一次是为了寻找某个结点的前驱节点，如下图所示，其中红色是为了定位到某个节点，黑色线是为了找到前驱节点，所以复杂度为O(n)。
前序遍历
- 1.设当前结点为cur
- 2.如果当前结点的左孩子为空，则输出当前结点并将其右孩子作为当前结点
- 3.如果当前结点的左孩子不为空，则找出左子树的最右结点，记为pre。
- 如果pre.right为空，则将pre.right指向当前结点，输出当前结点， 然后当前结点更新为当前结点的左孩子。
- 如果pre.right指向当前结点，则将pre.right重新设为空（恢复树的形状）， 然后当前结点更新为当前结点的右孩子。
- 4.重复步骤2、3，直到当前结点为空。
参考实现：
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
49
50
51
52
53
54
55
56
57
58
| package learn.binarytree.traverse;
import common.TreeNode;
import common.TreePrinter;
public class MorrisPreorderTraversal {
public void preorder(TreeNode root) {
TreeNode cur = root, pre;
while (cur != null) {
if (cur.left == null) {
System.out.print(cur.val + " ");
cur = cur.right;
} else {
pre = cur.left;
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = cur;
System.out.print(cur.val + " ");
cur = cur.left;
} else {
pre.right = null;
cur = cur.right;
}
}
}
}
public static void main(String[] args) {
int[] pre = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
int[] in = new int[]{3, 2, 5, 4, 6, 1, 7, 9, 8};
TreeNode root = TreeNode.buildFromPreAndIn(pre, in);
TreePrinter.prtHorizontalStyle(root);
new MorrisPreorderTraversal().preorder(root);
}
}
|
后序遍历
- 1.创建一个临时结点dump，令其左孩子是root，设当前结点为cur
- 2.如果当前结点的左孩子为空，则将其右孩子作为当前结点。
- 3.如果当前结点的左孩子不为空，则找出左子树的最右结点，记为pre。
- 如果pre.right为空，则将pre.right指向当前结点， 然后当前结点更新为当前结点的左孩子。
- 如果pre.right指向当前结点，则将pre.right重新设为空（恢复树的形状）， 倒序输出从当前节点的左孩子到pre这条路径上的所有节点， 然后当前结点更新为当前结点的右孩子。
- 4.重复步骤2、3，直到当前结点为空。
参考实现：
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| package learn.binarytree.traverse;
import common.TreeNode;
import common.TreePrinter;
public class MorrisPostorderTraversal {
public void postorder(TreeNode root) {
TreeNode dump = new TreeNode(0);
dump.left = root;
TreeNode cur = dump, pre;
while (cur != null) {
if (cur.left == null) {
cur = cur.right;
} else {
pre = cur.left;
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = cur;
cur = cur.left;
} else {
pre.right = null;
printReverse(cur.left);
cur = cur.right;
}
}
}
}
private void printReverse(TreeNode root) {
TreeNode head = reverse(root);
TreeNode node = head;
while (node != null) {
System.out.print(node.val + " ");
node = node.right;
}
reverse(head);
}
private TreeNode reverse(TreeNode root) {
TreeNode pre = null, cur = root;
while (cur != null) {
TreeNode next = cur.right;
cur.right = pre;
pre = cur;
cur = next;
}
return pre;
}
public static void main(String[] args) {
int[] in = new int[]{1, 5, 2, 4, 3, 9, 8, 6, 7};
int[] post = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
TreeNode root = TreeNode.buildFromInAndPost(in, post);
TreePrinter.prtHorizontalStyle(root);
new MorrisPostorderTraversal().postorder(root);
}
}
|
References
https://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html
https://en.wikipedia.org/wiki/Tree_traversal#Morris_in-order_traversal_using_threading