forked from algorithmzuo/algorithmbasic2020
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCode01_IsCBT.java
More file actions
120 lines (105 loc) · 2.96 KB
/
Code01_IsCBT.java
File metadata and controls
120 lines (105 loc) · 2.96 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
package class13;
import java.util.LinkedList;
// 测试链接 : https://leetcode.com/problems/check-completeness-of-a-binary-tree/
public class Code01_IsCBT {
// 不要提交这个类
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int v) {
val = v;
}
}
public static boolean isCompleteTree1(TreeNode head) {
if (head == null) {
return true;
}
LinkedList<TreeNode> queue = new LinkedList<>();
// 是否遇到过左右两个孩子不双全的节点
boolean leaf = false;
TreeNode l = null;
TreeNode r = null;
queue.add(head);
while (!queue.isEmpty()) {
head = queue.poll();
l = head.left;
r = head.right;
if (
// 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
(leaf && (l != null || r != null)) || (l == null && r != null)
) {
return false;
}
if (l != null) {
queue.add(l);
}
if (r != null) {
queue.add(r);
}
if (l == null || r == null) {
leaf = true;
}
}
return true;
}
public static boolean isCompleteTree2(TreeNode head) {
return process(head).isCBT;
}
public static class Info {
public boolean isFull;
public boolean isCBT;
public int height;
public Info(boolean full, boolean cbt, int h) {
isFull = full;
isCBT = cbt;
height = h;
}
}
public static Info process(TreeNode x) {
if (x == null) {
return new Info(true, true, 0);
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
boolean isCBT = false;
if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height) {
isCBT = true;
} else if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
isCBT = true;
} else if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
isCBT = true;
} else if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
isCBT = true;
}
return new Info(isFull, isCBT, height);
}
// for test
public static TreeNode generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
public static TreeNode generate(int level, int maxLevel, int maxValue) {
if (level > maxLevel || Math.random() < 0.5) {
return null;
}
TreeNode head = new TreeNode((int) (Math.random() * maxValue));
head.left = generate(level + 1, maxLevel, maxValue);
head.right = generate(level + 1, maxLevel, maxValue);
return head;
}
public static void main(String[] args) {
int maxLevel = 5;
int maxValue = 100;
int testTimes = 1000000;
for (int i = 0; i < testTimes; i++) {
TreeNode head = generateRandomBST(maxLevel, maxValue);
if (isCompleteTree1(head) != isCompleteTree2(head)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}