PTA甲级——树的同构 (25分)_pta go语言 树的同构 (25 分)

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UdcdtWph-1605802792125)(~/28)]

图1

图2
现给定两棵树，请你判断它们是否是同构的。
输入格式:

输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。
输出格式:

如果两棵树是同构的，输出“Yes”，否则输出“No”。
输入样例1（对应图1）：

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

输出样例1:

Yes

解题关键：原树和新树每对父节子结点的对应关系不变
可以从两个角度看代上面的话：
（1）找到原树和新树唯一对应的关系之后（这点非常重要，本题是每个结点对应的字母），每个父结点拥有不变的子节点。
（2）每个子结点拥有不变的父节点。
这里选则角度1。

其次注意使用邻结矩阵建树时需要自己寻找根节点。
寻找方法：由于根节点不存在父亲，所以输入的子结点信息只不包括根节点。可以利用这一点和根的编号为等差数列的性质来计算出根节点。

我在这里用dfs搜索保存了每个结点的子节点信息用于判断是否同构，实际上还可以使用递归判断。

代码实现及注释

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

char node1[15], node2[15]; //用来保存输入结点字符（这个其实没有用）
int t, root1, root2; //记录两棵树的根所在的位置,和结点数量
int tree1[15][2], tree2[15][2]; //记录树的关系
vector<int> f1[100], f2[100]; //保存两颗树父节点的信息，用字母标识

int build(char* node, int tree[][2]) //注意一下将二维矩阵作为参数的定义方法
{
	int root;
	char f, s1, s2;
	root = t * (t - 1) / 2;
	for (int i = 0; i < t; i++)
	{
		scanf("%c %c %c\n", &f, &s1, &s2);
		node[i] = f;
		tree[i][0] = (isdigit(s1)) ? s1 - '0' : -1;
		tree[i][1] = (isdigit(s2)) ? s2 - '0' : -1;
		if (tree[i][0] != -1) root -= tree[i][0];
		if (tree[i][1] != -1) root -= tree[i][1];
	}
	return root;
}

void getson(int root, char* node, int tree[][2], vector<int>* fx) //需要使用字符来进行对应，因为在输入信息时，根节点的编号可以改变，只可以使用字母唯一标识
{
	if (root == -1) return;
	if (tree[root][0] != -1) fx[node[root]].push_back(node[tree[root][0]]);
	if (tree[root][1] != -1) fx[node[root]].push_back(node[tree[root][1]]);
	getson(tree[root][0], node, tree, fx);
	getson(tree[root][1], node, tree, fx);
}

int main() 
{
	scanf("%d\n", &t);
	if (t == 0) { cout << "Yes"; return 0; }
	else if (t == 1) { cout << "No"; return 0; }
	root1 = build(node1, tree1);
	scanf("%d\n", &t);
	root2 = build(node2, tree2);

	getson(root1, node1, tree1, f1);
	getson(root2, node2, tree2, f2);

	int sign = 1;
	for (int i = 0; i < t; i++)
	{
		if (f1[node1[i]].size() != f2[node1[i]].size()) { sign = 0; break; }
		sort(f1[node1[i]].begin(), f1[node1[i]].end());
		sort(f2[node1[i]].begin(), f2[node1[i]].end());
		for (int j = 0; j < f1[node1[i]].size(); j++)
			if (f1[node1[i]][j] != f2[node1[i]][j]) { sign = 0; break; }
	}
	if (sign) cout << "Yes";
	else cout << "No";

	return 0;
}
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