题目描述
给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图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
输入样例2(对应图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
分析
1.存储二叉树
一般会使用链表来存储二叉树,但这里因为要等到所有的结点输入完毕后才能知道头结点是哪个(第一个样例第二组输入),所以这里使用链表不是很方便
因此这里使用了静态链表的方式存储,也就是使用结构体数组,每个结构体是一个结点,其中包含数据域和两个指针域,指针域分别指向左孩子和右孩子在数组中的位置。
也可以使用顺序表(数组)的方式存储二叉树,只需要将其看成是完全二叉树即可
2.判断树是否同构
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 int equaltree (int now0,int now1) { if (now0 == -1 && now1 == -1 ) return 1 ; if ((now0 == -1 && now1 != -1 ) || (now0 != -1 && now1 == -1 )) return 0 ; if (bintrees[0 ][now0].data != bintrees[1 ][now1].data) return 0 ; if ((bintrees[0 ][now0].lChildpos == -1 ) && (bintrees[1 ][now1].lChildpos == -1 )) return equaltree(bintrees[0 ][now0].rChildpos, bintrees[1 ][now1].rChildpos); if ((bintrees[0 ][now0].lChildpos != -1 ) && (bintrees[1 ][now1].lChildpos != -1 ) && (bintrees[0 ][bintrees[0 ][now0].lChildpos].data == bintrees[1 ][bintrees[1 ][now1].lChildpos].data)) return (equaltree(bintrees[0 ][now0].lChildpos, bintrees[1 ][now1].lChildpos) && equaltree(bintrees[0 ][now0].rChildpos, bintrees[1 ][now1].rChildpos)); else return (equaltree(bintrees[0 ][now0].lChildpos, bintrees[1 ][now1].rChildpos) && equaltree(bintrees[0 ][now0].rChildpos, bintrees[1 ][now1].lChildpos)); }
这个函数的核心思想是每次调用equaltree,都可以把now0和now1所指向的结点看成一颗树的根节点
在两个根节点相同的情况下,下一步要做的就是判断左子树和右子树是否匹配,如果最终两棵树同构的话只有两种可能:
左子树之间同构,右子树之间同构
左子树和右子树同构,右子树和左子树同构
基于以上两种可能,我们可以通过一个if提前预知是哪种可能:
1 2 3 4 5 6 7 if ((bintrees[0 ][now0].lChildpos != -1 ) && (bintrees[1 ][now1].lChildpos != -1 ) && (bintrees[0 ][bintrees[0 ][now0].lChildpos].data == bintrees[1 ][bintrees[1 ][now1].lChildpos].data)) return (equaltree(bintrees[0 ][now0].lChildpos, bintrees[1 ][now1].lChildpos) && equaltree(bintrees[0 ][now0].rChildpos, bintrees[1 ][now1].rChildpos)); else return (equaltree(bintrees[0 ][now0].lChildpos, bintrees[1 ][now1].rChildpos) && equaltree(bintrees[0 ][now0].rChildpos, bintrees[1 ][now1].lChildpos));
如果不提前判断是哪种可能的话,也可直接暴力匹配一遍,也就是直接把两种可能
1 2 3 return (equaltree(bintrees[0 ][now0].lChildpos, bintrees[1 ][now1].lChildpos) &&equaltree(bintrees[0 ][now0].rChildpos, bintrees[1 ][now1].rChildpos)) || (equaltree(bintrees[0 ][now0].lChildpos, bintrees[1 ][now1].rChildpos) &&equaltree(bintrees[0 ][now0].rChildpos, bintrees[1 ][now1].lChildpos));
这样也能通过,只是时间从4ms变成了16ms
代码
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 79 #include <iostream> using namespace std ;struct TreeNode { char data; int lChildpos,rChildpos; }; struct TreeNode bintrees [2][20]; int buildTree (int i) { int n; char data, lChildpos, rChildpos; int checked[20 ] = { 0 }; cin >> n; for (int j = 0 ; j < n; j++) { cin >> data >> lChildpos >> rChildpos; bintrees[i][j].data = data; if (lChildpos != '-' ) { bintrees[i][j].lChildpos = lChildpos - '0' ; checked[bintrees[i][j].lChildpos] = 1 ; } else bintrees[i][j].lChildpos = -1 ; if (rChildpos != '-' ) { bintrees[i][j].rChildpos = rChildpos - '0' ; checked[bintrees[i][j].rChildpos] = 1 ; } else bintrees[i][j].rChildpos = -1 ; } for (int j = 0 ; j < n; j++) { if (checked[j] == 0 ) return j; } return -1 ; } int equaltree (int now0,int now1) { if (now0 == -1 && now1 == -1 ) return 1 ; if ((now0 == -1 && now1 != -1 ) || (now0 != -1 && now1 == -1 )) return 0 ; if (bintrees[0 ][now0].data != bintrees[1 ][now1].data) return 0 ; if ((bintrees[0 ][now0].lChildpos == -1 ) && (bintrees[1 ][now1].lChildpos == -1 )) return equaltree(bintrees[0 ][now0].rChildpos, bintrees[1 ][now1].rChildpos); if ((bintrees[0 ][now0].lChildpos != -1 ) && (bintrees[1 ][now1].lChildpos != -1 ) && (bintrees[0 ][bintrees[0 ][now0].lChildpos].data == bintrees[1 ][bintrees[1 ][now1].lChildpos].data)) return (equaltree(bintrees[0 ][now0].lChildpos, bintrees[1 ][now1].lChildpos) && equaltree(bintrees[0 ][now0].rChildpos, bintrees[1 ][now1].rChildpos)); else return (equaltree(bintrees[0 ][now0].lChildpos, bintrees[1 ][now1].rChildpos) && equaltree(bintrees[0 ][now0].rChildpos, bintrees[1 ][now1].lChildpos)); } int main () { int root0, root1; root0 = buildTree(0 ); root1 = buildTree(1 ); if (equaltree(root0, root1)) cout << "Yes" << endl ; else cout << "No" << endl ; return 0 ; }