判断完全二叉树
判断完全二叉树
题设
问题描述
假设二叉树中的每个结点值为单个整数,采用二叉链结构存储,设计算法判断给定的二叉树是否是完全二叉树。假定每棵二叉树节点不超过2000个。
输入形式
每个测试是一颗二叉树的括号表示法字符串
输出形式
如果是完全二叉树,输出“1”;如果不是完全二叉树,输出“0”
样例输入
1
1(2(4,5),3)
样例输出
1
1
题解
先建树,这里依然是用的l数组和r数组。建完树之后用BFS判断是否是完全二叉树,方法是当出现子树为空时,记录一下,若之后出现非空子树,那么一定是非完全二叉树
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
#include <iostream>
using namespace std;
const int N = 100010;
int l[N], r[N], e[N], q[N], root, idx;
char line[N];
int pars(char *&s) {
if (*s == '\0' || !isdigit(*s)) return 0;
int u = ++idx;
int val = 0;
while (isdigit(*s)) {
val = val * 10 + (*s - '0');
s++;
}
e[idx] = val;
if (*s == '(') {
s++;
l[u] = pars(s);
if (*s == ',') {
s++;
r[u] = pars(s);
}
if (*s == ')') {
s++;
}
}
return u;
}
bool check_complete(int root) {
if (!root) return true;
int hh = 0, tt = 0;
q[0] = root;
bool flag = false;
while (hh <= tt) {
int t = q[hh++];
if (l[t]) {
if (flag) return false;
q[++tt] = l[t];
} else
flag = true;
if (r[t]) {
if (flag) return false;
q[++tt] = r[t];
} else
flag = true;
}
return true;
}
int main() {
// freopen("in.txt", "r", stdin);
scanf("%s", line);
char *input = line;
root = pars(input);
if (check_complete(root))
puts("1");
else
puts("0");
return 0;
}
This post is licensed under CC BY 4.0 by the author.