二叉树的同构

附上题目链接:

二叉树的同构

理解:

只要确保每个节点和其左右孩子的结点相等,或者孩子交换之后相等就可以。
只要每个结点都符合,那么整棵树自然从上到下就都符合。

code:
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
 #include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 20;
struct node{
char key;
int left, right;
}tree1[maxn], tree2[maxn]; //构建一个结构体用来构建两个二叉树
int n1, n2;
void build_tree(struct node * tree, int n){
int i;
char s[2];
for (i = 0; i < n; i++){
cin >> s;
tree[i].key = s[0];
cin >> s;
if (s[0] == '-'){
tree[i].left = 11; //如果输入为 - 则置为一个非0到10的数
}
else{
tree[i].left = s[0] - '0'; //字符向数字转换
}
cin >> s;
if (s[0] == '-'){
tree[i].right = 11;
}
else{
tree[i].right = s[0] - '0';
}
}
}
bool checkc(int i, int j){ //检测key相同的两个结点的左右孩子是否相同或者交换后是否相同
if (tree1[tree1[i].left].key == tree2[tree2[j].left].key&&tree1[tree1[i].right].key == tree2[tree2[j].right].key)
{
return 1;
}
if (tree1[tree1[i].left].key == tree2[tree2[j].right].key&&tree1[tree1[i].right].key == tree2[tree2[j].left].key)
{
return 1;
}
return 0;
}
bool check(){
int i, j; //找到key相同的结点
for (i = 0; i < n1; i++){
for (j = 0; j < n2; j++){
if (tree1[i].key == tree2[j].key){
if (checkc(i, j)){
break; //孩子相同或者交换后相同继续下一个结点
}
else{
return 0;
}
}
}
if (j == n2){
return 0; //没找到
}
}
return 1; //整棵二叉树都符合条件
}
int main(){
while (cin>>n1){
build_tree(tree1, n1);
cin>>n2;
build_tree(tree2, n2);
if (n2!=n1){
cout << "No"<<endl;
}
else if (check()){
cout << "Yes"<<endl;
}
else{
cout << "No"<<endl;
}
}
return 0;
}
0%