时间:2021年11月9日
作者:返祖猿
题目集:数据结构与算法题目集(中文)
题目:7-3 树的同构 (25 分)
我居然解出一道树的题!!!
我很激动!!!
我准备趁热打铁把想法记录在这儿,如有雷同纯属偶然。
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 -
Yes
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
No
#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; } }
嗐,我自己都觉得这代码太长,真的有人看么 (←_←)
先不管其他的,读完输入后发现它的 根节点 都不按顺序给出来,着实劝退……
然后注意到根节点一定不会在每行输入的后两个数字中出现,于是用了一个很笨的方法寻找根节点:把输入的后两列数字记录,没有出现的那个数字就是根节点。
事实证明这个方法很好用~
实现输入后开始思考如何实现判断两棵树同构的方法。
同构的最大特点就是两棵树同一节点的两个孩子相同,但顺序不同,然而一个节点有两个孩子,判断两个节点的两个孩子是否一样,还是稍微有点绕的。
此处解释一下我为什么要用递归呢,因为用 while 我不会写……咳,真的,有时会觉得递归比 while 还简单,这肯定不是我一个人的想法。
但是实现递归的时候就不会这么想了。
另外,也想过某个字节点的两个孩子里放的字符一样的情况,但从常识上考虑出题人应该不会如此疯狂……吧??姑且还是忽略了。
事实证明确实想太多,疯狂的只有我而已。
当继续向下写的时候就要开始考虑答题了。
再读一遍题,我发现题目没有明说两棵树的节点不可能为 0,于是又仔细看了一遍,发现题目真的没有明说两棵树的节点不为 0,emmm,姑且写上了输出 “No”,提交一遍后发现专门有个测试点专门针对这种情况,而答案是 “Yes”,我竟无言以对。
当节点只有一个的时候,题目是很简单的。
如果两棵树的节点数不一样的话,这两棵树肯定是不同构的,为此还得定义 m 来控制第二课树的输入。需要注意的是,如果输入第二个节点数后立即判断、输出并 return,而不接收第二棵树的节点,pta 会因为没有完全接收它给出的数据而判错,这是另一道题的前车之鉴了。
没错,我连这种错都范过……
此外,多节点的情况下,根节点保存的字符不同也是显而易见的不同构,这同时解决了第一次进入递归的初始化问题。
一时也想不到其他显而易见的错误了,于是回过头来继续做题。
因为是用递归写的代码,所以要好好规划一下这递归究竟如何使用:
其实简单写下的规定还是有不明朗之处,但一时间也想不到许多,于是先把两个节点两个孩子的判断代码搬入递归方法中。方法名是 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 语句。
其实加上 ( ) () () 就没问题了。
当写完只有一个孩子的情况,发现还有个 “节点无孩子” 在等着我,简直累感不爱。
不过代码都已经完成到这一步了,难道还要退缩吗?No.
写只有一个孩子的情况时就想到,如果两个节点的孩子数不同,两节点同样不同构,于是加上了这条判断。
这里还有个小失误,因为 countChildren 返回 1 也返回 -1,得给它套个 abs 才能放心比较,纠错时常 + 20min。
节点无孩子倒是简单,因为规定了进入递归的两节点是同构的,直接返回 1。
至此,递归方法结束。
检查一遍主方法后,主方法也结束了。
因为写代码的时候比较细心,六个监测点里只错了一个,还是因为空树返回 Yes 或 No 而错的,说实话有点小开心。这里要是错一大片简直崩溃。
倒是测试用例的时候纠错好长时间,无语无语,冷静冷静,兜住兜住━━( ̄ー ̄*|||━━
这不是第一次做出 25 分的题,但是第一次做对树,很有成就感。
至今连根据前序遍历和中序遍历推导树的结构都做不到。
各位看官要是有感而发,欢迎评论区分享。
没有的话就算了,毕竟我也不看这种又臭又长的文(doge
千言万语无墨可落,不必关注,有缘再见。
黑历史 + 1