-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMorris.java
More file actions
170 lines (159 loc) · 5.76 KB
/
Morris.java
File metadata and controls
170 lines (159 loc) · 5.76 KB
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
package _aTemplate;
// IMP: Morris遍历, T: O(N), S: O(1)
public class Morris {
public static class Node {
public int val;
public Node left;
public Node right;
public Node(int v) {
val = v;
}
}
// 0523
public static void morris(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;
}
// mostRight : 一定是当前节点左树上的最右节点
// 情况1: 第一次来到当前节点
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
}
// 情况2: 第二次来到, mostRight.right == cur
mostRight.right = null;
}
// 第二次来到当前节点
// 1. 没有左树向右移动
// 2. mostRight.right == cur, 恢复, 往右跳
cur = cur.right;
}
}
// Morris先序遍历, 一个节点在第一次到达自己就打印
// 1. 节点无左树, 只能到自己一次, 刚到他就打印
// 2. 节点有左树, 第一次到达时候打印
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.right == null) {
// 情况2. 节点有左树, 第一次到达时候打印
System.out.println(cur.val + " ");
mostRight.right = cur;
cur = cur.left;
continue;
}
// mostRight.right == cur
mostRight.right = null;
} else {
// 情况1. 没左树, 第一次到达时候就打印
System.out.println(cur.val + " ");
}
// 1. 没有左树向右移动
// 2. mostRight.right == cur, 恢复, 往右跳
cur = cur.right;
}
}
// Morris中序遍历, 一个节点在第二次来到自己时候打印
// 1.没有左树, 直接打印
// 2.有左树, 第二次来到自己打印
public static void morrisIn(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.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
}
// mostRight.right == cur
mostRight.right = null;
}
// 1. 没有左树向右移动
// 2. 有左树, 到自己两次
System.out.println(cur.val + " ");
cur = cur.right;
}
}
// Morris实现后序遍历
// NOTE: 把处理时机放在能回到自己两次的节点且第二次回到自己的时候
// 第二次回到自己的时候, 逆序打印他左树右边界(使用链表翻转)
// 在Morris遍历跑完之后, 单独打印整棵树的右边界
public static void morrisPost(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; // 不断往右
}
// mostRight 一定是左树最右节点, 但是有两种情况
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
}
// mostRight.right == cur
mostRight.right = null; // 恢复, 指向空
// 第二次回到自己的时候, 逆序打印自己的左树右边界
printEdge(cur.left);
}
cur = cur.right;
}
// 最后不要忘了逆序打印整棵树的右边界
printEdge(head);
}
// 打印node节点的左树右边界
private static void printEdge(Node head) {
Node tail = reverseEdge(head); // 再次翻转回来用
Node cur = tail;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.right;
}
// 打完之后再翻转回来
reverseEdge(tail);
}
// 链表翻转
private static Node reverseEdge(Node head) {
Node pre = null;
Node next = null;
while (head != null) {
next = head.right;
head.right = pre;
pre = head;
head = next;
}
return pre;
}
}