二叉树的同构

发表于 | 分类于
字数统计: 474 word | 阅读时长 ≈ 2 min
附上题目链接：

二叉树的同构

理解：

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

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%