7-3 树的同构
时间：2021年11月9日
作者：返祖猿
题目集：数据结构与算法题目集（中文）
题目：7-3 树的同构 (25 分)
1、前言
我居然解出一道树的题！！！
我很激动！！！
我准备趁热打铁把想法记录在这儿，如有雷同纯属偶然。
2、题目
输入样例 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
输入样例 2
8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4
输出样例 2
No
3、代码
#include<stdio.h>
typedef struct node{
int id;
char c;
struct node *left;
struct node *right;
} P;
int countChildren(P *pa);
int answer(P *pa, P *pb);
int main(){
// 定义变量
P pa[10], pb[10];
P *rootA, *rootB;
int flagA[10] = {}, flagB[10] = {};
int m, n, i;
char temp;
// 控制输入 1
scanf("%d", &n);
for(i=0; i<n; i++){
pa[i].id = i;
// 左节点
scanf("\n%c %c ", &pa[i].c, &temp);
if(isdigit(temp)){
pa[i].left = &pa[temp-'0'];
flagA[temp-'0'] = 1;
} else {
pa[i].left = NULL;
}
// 右节点
scanf("%c", &temp);
if(isdigit(temp)){
pa[i].right = &pa[temp-'0'];
flagA[temp-'0'] = 1;
} else {
pa[i].right = NULL;
}
}
// 控制输入 2
scanf("%d", &m);
for(i=0; i<m; i++){
pb[i].id = i;
// 左节点
scanf("\n%c %c ", &pb[i].c, &temp);
if(isdigit(temp)){
pb[i].left = &pb[temp-'0'];
flagB[temp-'0'] = 1;
} else {
pb[i].left = NULL;
}
// 右节点
scanf("%c", &temp);
if(isdigit(temp)){
pb[i].right = &pb[temp-'0'];
flagB[temp-'0'] = 1;
} else {
pb[i].right = NULL;
}
}
// ----------------------------------------------------------------
// 排除显而易见的不同构树
if(n != m){
printf("No");
return 0;
}
if(n == 1){
if(pa[0].c != pb[0].c){
printf("No");
} else {
printf("Yes");
}
return 0;
}
if(n == 0){
printf("Yes");
return 0;
}
// 寻找两棵树的根节点
for(i=0; i<n; i++){
if(flagA[i] == 0){
rootA = &pa[i];
}
if(flagB[i] == 0){
rootB = &pb[i];
}
}
// test: 测试根节点是否正确
// printf("rootA: %d %c\n", rootA->id, rootA->c);
// printf("rootB: %d %c\n", rootB->id, rootB->c);
// true
// 判断根节点是否相同
if(rootA->c != rootB->c){
printf("No");
return 0;
}
if(answer(rootA, rootB) == 0){
printf("No");
} else {
printf("Yes");
}
return 0;
}
// 此方法判断节点有几个孩子
int countChildren(P *pa){
int count = 2;
if(pa->left == NULL) count--;
if(pa->right == NULL) count--;
if(count == 2){
return 2;
} else if(count == 0){
return 0;
} else if(pa->left != NULL){
return -1;
} else if(pa->right != NULL){
return 1;
}
}
// 此方法递归判断两棵树的各节点的孩子是否相同
int answer(P *pa, P *pb){
int countA = countChildren(pa);
int countB = countChildren(pb);
P *tempA, *tempB;
char pal, par, pbl, pbr;
// 孩子数不同则不同构
if(abs(countA) != abs(countB)){
return 0;
}
// 全是叶子节点的情况，因为送进来之前已经判断了两个节点相同，所以返回 1
if(countA == 0 && countB == 0){
return 1;
}
// 都只有一个孩子的情况，这两个孩子保存的字符必须相同
if(countA != 2){
if(countA>0){
tempA = pa->right;
} else {
tempA = pa->left;
}
if(countB>0){
tempB = pb->right;
} else {
tempB = pb->left;
}
// printf("\n%c %c\n", tempA->c, tempB->c);
// note: return 的话程序就结束了，所以不会从这里进入两个孩子的情况
if(tempA->c == tempB->c){
return answer(tempA, tempB);
} else {
return 0;
}
}
// 两个孩子的情况
pal = pa->left->c;
par = pa->right->c;
pbl = pb->left->c;
pbr = pb->right->c;
// printf("\n%c %c %c %c\n", pal, par, pbl, pbr);
// note: 应该没有左右孩子相同的情况，吧……
if((pal == pbl || pal == pbr)&&(par == pbl || par == pbr)){
if(pal == pbl){
return answer(pa->left, pb->left) && answer(pa->right, pb->right);
} else {
return answer(pa->left, pb->right) && answer(pa->right, pb->left);
}
} else {
return 0;
}
}
嗐，我自己都觉得这代码太长，真的有人看么 (←_←)
4、思考过程
① 寻找根节点
先不管其他的，读完输入后发现它的 根节点 都不按顺序给出来，着实劝退……
然后注意到根节点一定不会在每行输入的后两个数字中出现，于是用了一个很笨的方法寻找根节点：把输入的后两列数字记录，没有出现的那个数字就是根节点。
事实证明这个方法很好用~
② 实现检查同构
实现输入后开始思考如何实现判断两棵树同构的方法。
a. 寻找检查两个节点的两个孩子相同但顺序不同的方法
同构的最大特点就是两棵树同一节点的两个孩子相同，但顺序不同，然而一个节点有两个孩子，判断两个节点的两个孩子是否一样，还是稍微有点绕的。
- 先在纸上写出了四个变量：pal, par, pbl, pbr，分别表示四个孩子；
- 然后推出两个节点的两个孩子相同的判别式：(pal == pbl || pal == pbr) && (par == pbl || par == pbr)；
- 满足判别式的两个节点进入下一场递归：
- if(pal == pbl) return answer(pa->left, pb->left) && answer(pa->right, pb->right);
- else return answer(pa->left, pb->right) && answer(pa->right, pb->left);
此处解释一下我为什么要用递归呢，因为用 while 我不会写……咳，真的，有时会觉得递归比 while 还简单，这肯定不是我一个人的想法。
但是实现递归的时候就不会这么想了。
另外，也想过某个字节点的两个孩子里放的字符一样的情况，但从常识上考虑出题人应该不会如此疯狂……吧？？姑且还是忽略了。
事实证明确实想太多，疯狂的只有我而已。
b. 排除显而易见的错误答案
当继续向下写的时候就要开始考虑答题了。
再读一遍题，我发现题目没有明说两棵树的节点不可能为 0，于是又仔细看了一遍，发现题目真的没有明说两棵树的节点不为 0，emmm，姑且写上了输出 “No”，提交一遍后发现专门有个测试点专门针对这种情况，而答案是 “Yes”，我竟无言以对。
当节点只有一个的时候，题目是很简单的。
如果两棵树的节点数不一样的话，这两棵树肯定是不同构的，为此还得定义 m 来控制第二课树的输入。需要注意的是，如果输入第二个节点数后立即判断、输出并 return，而不接收第二棵树的节点，pta 会因为没有完全接收它给出的数据而判错，这是另一道题的前车之鉴了。
没错，我连这种错都范过……
此外，多节点的情况下，根节点保存的字符不同也是显而易见的不同构，这同时解决了第一次进入递归的初始化问题。
c. 实现递归方法的主体内容
一时也想不到其他显而易见的错误了，于是回过头来继续做题。
因为是用递归写的代码，所以要好好规划一下这递归究竟如何使用：
- 规定：进入递归的两个节点所保存的字符是相同的，即两个节点是同构的，孩子不论。
- 二、递归判断的是两个节点的孩子是否保存着相同的字符，即判断孩子的同构。
- 三、return 的是……emmm……一时间想不通这条咋叙述，所以 pass。
其实简单写下的规定还是有不明朗之处，但一时间也想不到许多，于是先把两个节点两个孩子的判断代码搬入递归方法中。方法名是 answer，因为一时间也想不到什么好名字了，甚至连写个 answer 都要百度咋拼。
写着写着忽然想到，一个节点不一定有两个孩子，还有可能没有孩子，甚至另一个孩子是根本就不是节点（而是 NULL），一时间觉得写递归的难度飙升，劝退*2。
于是梳理了一下我的递归到底在写什么，记录下三条分支：
- 每节点一个孩子；
- 每个节点俩个孩子；
- 节点无孩子；
废话文学实锤。
两个孩子的情况 pass。
当节点只有一个孩子时，首先要判断究竟是哪个孩子不是孩子（递归码字进行时），即另一个孩子是 NULL。
于是改了之前写的一个 判断两个节点保存的字符是否相同 的方法，来判断某个节点有几个孩子，方便起见，当节点的左孩子为 NULL 时返回 1，右孩子为 NULL 时返回 -1，是参考的横轴左负右正。结果后来还是用错了，纠错时长 + 20min。 方法名 countChildren。
countA = countChildren(pa)，pb 同处理。
真正动手判断的时候甚至想过 char tempA = countA>0?pa->right->c:pa->right->c 这种扭曲写法，事实证明代码过于集成反而麻烦，于是改为 P tempA = countA>0?pa->right:pa->right，发现写到 right 的时候编译器没有及时提示，惊觉不靠谱，最终改成了简朴的 if 语句。
其实加上 ( ) () () 就没问题了。
d. 完善递归方法
当写完只有一个孩子的情况，发现还有个 “节点无孩子” 在等着我，简直累感不爱。
不过代码都已经完成到这一步了，难道还要退缩吗？No.
写只有一个孩子的情况时就想到，如果两个节点的孩子数不同，两节点同样不同构，于是加上了这条判断。
这里还有个小失误，因为 countChildren 返回 1 也返回 -1，得给它套个 abs 才能放心比较，纠错时常 + 20min。
节点无孩子倒是简单，因为规定了进入递归的两节点是同构的，直接返回 1。
至此，递归方法结束。
③ 最终梳理程序
检查一遍主方法后，主方法也结束了。
因为写代码的时候比较细心，六个监测点里只错了一个，还是因为空树返回 Yes 或 No 而错的，说实话有点小开心。这里要是错一大片简直崩溃。
倒是测试用例的时候纠错好长时间，无语无语，冷静冷静，兜住兜住━━(￣ー￣*|||━━
5、后记
这不是第一次做出 25 分的题，但是第一次做对树，很有成就感。
至今连根据前序遍历和中序遍历推导树的结构都做不到。
各位看官要是有感而发，欢迎评论区分享。
没有的话就算了，毕竟我也不看这种又臭又长的文（doge
千言万语无墨可落，不必关注，有缘再见。
黑历史 + 1