forked from morethink/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathBinaryTree.java
More file actions
244 lines (223 loc) · 6.71 KB
/
BinaryTree.java
File metadata and controls
244 lines (223 loc) · 6.71 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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
package algorithm.tree;
import java.util.Stack;
/**
* @author 李文浩
* @version 2017/7/30.
*/
public class BinaryTree {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public static void main(String[] args) {
TreeNode treeNode1 = new TreeNode(1);
TreeNode treeNode2 = new TreeNode(2);
TreeNode treeNode3 = new TreeNode(3);
TreeNode treeNode4 = new TreeNode(4);
TreeNode treeNode5 = new TreeNode(5);
TreeNode treeNode6 = new TreeNode(6);
treeNode1.left = treeNode2;
treeNode1.right = treeNode3;
treeNode2.left = treeNode4;
treeNode2.right = treeNode5;
treeNode3.left = treeNode6;
System.out.println("高度:" + height(treeNode1));
// System.out.println("先序递归");
// preOrder(treeNode1);
// System.out.println();
// System.out.println("中序递归");
// inOrder(treeNode1);
// System.out.println();
System.out.println("后序递归");
postOrder(treeNode1);
System.out.println();
// System.out.println("先序非递归");
// preStack(treeNode1);
// System.out.println();
// System.out.println("先序非递归2");
// preStack2(treeNode1);
// System.out.println();
// System.out.println("中序非递归");
// inStack(treeNode1);
// System.out.println();
System.out.println("后序非递归");
postStack(treeNode1);
System.out.println();
System.out.println("后序非递归2");
postStack2(treeNode1);
System.out.println();
}
public static int height(TreeNode node) {
TreeNode left = node.left, right = node.right;
if (left == null && right == null) {
return 1;
}
if (left == null && right != null) {
return height(right) + 1;
}
if (right == null && left != null) {
return height(left) + 1;
}
int leftHeight = height(left);
int rightHeight = height(right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
/**
* 先序递归
*
* @param treeNode
*/
public static void preOrder(TreeNode treeNode) {
if (treeNode != null) {
System.out.print(treeNode.val + " ");
preOrder(treeNode.left);
preOrder(treeNode.right);
}
}
/**
* 中序递归
*
* @param treeNode
*/
public static void inOrder(TreeNode treeNode) {
if (treeNode != null) {
inOrder(treeNode.left);
System.out.print(treeNode.val + " ");
inOrder(treeNode.right);
}
}
/**
* 后序递归
*
* @param treeNode
*/
public static void postOrder(TreeNode treeNode) {
if (treeNode != null) {
postOrder(treeNode.left);
postOrder(treeNode.right);
System.out.print(treeNode.val + " ");
}
}
/**
* 先序非递归
*
* @param root
*/
public static void preStack(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode treeNode = stack.pop();
System.out.print(treeNode.val + " ");
if (treeNode.right != null) {
stack.push(treeNode.right);
}
if (treeNode.left != null) {
stack.push(treeNode.left);
}
}
}
/**
* 先序非递归2
*
* @param root
*/
public static void preStack2(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode treeNode = root;
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
System.out.print(treeNode.val + " ");
stack.push(treeNode);
treeNode = treeNode.left;
}
if (!stack.isEmpty()) {
treeNode = stack.pop();
treeNode = treeNode.right;
}
}
}
/**
* 中序非递归
*
* @param treeNode
*/
public static void inStack(TreeNode treeNode) {
Stack<TreeNode> stack = new Stack<>();
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
stack.push(treeNode);
treeNode = treeNode.left;
}
if (!stack.isEmpty()) {
treeNode = stack.pop();
System.out.print(treeNode.val + " ");
treeNode = treeNode.right;
}
}
}
public static class TagNode {
TreeNode treeNode;
boolean isFirst;
}
/**
* 后序非递归
*
* @param treeNode
*/
public static void postStack(TreeNode treeNode) {
Stack<TagNode> stack = new Stack<>();
TagNode tagNode;
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
tagNode = new TagNode();
tagNode.treeNode = treeNode;
tagNode.isFirst = true;
stack.push(tagNode);
treeNode = treeNode.left;
}
if (!stack.isEmpty()) {
tagNode = stack.pop();
if (tagNode.isFirst == true) {
tagNode.isFirst = false;
stack.push(tagNode);
treeNode = tagNode.treeNode.right;
} else {
System.out.print(tagNode.treeNode.val + " ");
treeNode = null;
}
}
}
}
/**
* 后序非递归2
*
* @param treeNode
*/
public static void postStack2(TreeNode treeNode) {
Stack<TreeNode> stack = new Stack<>();
TreeNode currentTreeNode;
TreeNode preTreeNode = null;
stack.push(treeNode);
while (!stack.isEmpty()) {
currentTreeNode = stack.peek();
if ((currentTreeNode.left == null && currentTreeNode.right == null) ||
(preTreeNode != null && (preTreeNode == currentTreeNode.left || preTreeNode == currentTreeNode.right))) {
System.out.print(currentTreeNode.val + " ");
stack.pop();
preTreeNode = currentTreeNode;
} else {
if (currentTreeNode.right != null) {
stack.push(currentTreeNode.right);
}
if (currentTreeNode.left != null) {
stack.push(currentTreeNode.left);
}
}
}
}
}