给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。
| 图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结尾无空行
输入样例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这道题的难点在于三个，一个怎么在给出的几行数字中找出根结点，第二个怎么用数组来表示这个二叉树，第三个就是怎么判断同构了，其实前两点在mooc陈越老师那儿都说过了，第三个判断还需要自己推敲一下，我先说一下我最先的思路：
首先判断根节点空不空，这就衍生出三个判断语句：两个都空（相等），一个空、一个不空（不等），都不空（下一堆判断）；
既然都不空，自然要进行接下来的判断：根结点不相等（不等），根节点相等（相等）；
根节点既然相等了，那么就要判断根节点的左子树和右子树了：这个时候同样的判断方法，先看空不空，再看等不等，刚开始我用了很多if语句，将四个空（两个根节点都有左右子树，就是4个）、三个空和一个空（这俩一样，都不等）、两个空、都不空（元素等不等）全都写上去分别判断，看着特别多，但再看了看mooc陈越老师的ppt，其实可以简化一下，我们可以从接下来的递归来倒推我们应该做什么判断：
1、（左，左）----> 当（右、右）为空时做的递归
2、（右、右）----> 当（左，左）为空时做的递归
3、（左，左）&&（右、右）---->当左不为空时，并且左子树元素还相等
4、（左，右）&&（右、左）---->左子树不相等（这种不等可能是因为一个空一个不空，也可能是都不空但不等，反正是一样的递归比较）；
（是不是想问为啥没有单独的（左，右）和（右、左）：
举个栗子，单独比较（左，右）是建立在（右、左）相等的情况下，这种情况不就是（左，左）不相等的情况啊，用4就能判断啊）
有没有发现，其实1号判断也不需要，因为2、3、4号判断的首要条件都是比较的（左，左），我认为是一个变量，那么也就是说1号所需要的专门比较（左，左）已经涵盖在里面了，我们最后需要的只是2、3、4号判断。
（总的来分析，作判断比较只需要一个变量）
在此题中，只需要确认（左，左）空不空、等不等的情况，其他的交给递归。
//树的同构
#include<stdio.h>
#define Maxtree 10
#define Null -1
#define Tree int
#define Elementype charstruct Tree_Node{
Elementype element;
Tree left;
Tree right;
} T1[Maxtree], T2[Maxtree];Tree BuildTree(struct Tree_Node T[]);
int Isomorphic(Tree R1, Tree R2);int main()
{
Tree R1, R2;
R1=BuildTree(T1);
R2=BuildTree(T2);
if(Isomorphic(R1,R2)) printf("Yes");
else printf("No");
return 0;
}Tree BuildTree(struct Tree_Node T[])
{
int i=0, N=0;
Tree root=Null;
scanf("%d", &N);
char cl, cr;
int check[N];
for( i = 0; i < N; i++ ) check[i] = 0;
for(i=0;i<N;i++){
scanf("\n%c %c %c", &T[i].element, &cl, &cr);
if(cl!='-'){
T[i].left=cl-'0';
check[T[i].left]=1;
}
else T[i].left=Null;
if(cr!='-'){
T[i].right=cr-'0';
check[T[i].right]=1;
}
else T[i].right=Null;
}
for(i=0;i<N;i++){
if(!check[i]) {
root=i;
break;
}
}
return root;
}int Isomorphic(Tree R1, Tree R2)
{
if(R1==Null&&R2==Null) return 1;
if(R1!=Null&&R2==Null || R2!=Null&&R1==Null) return 0;
if(R1!=Null && R2!=Null){
if(T1[R1].element!=T2[R2].element) return 0;
else{
if(T1[R1].left==Null && T2[R2].left==Null) return Isomorphic(T1[R1].right, T2[R2].right);
if(T1[R1].left!=Null && T2[R2].left!=Null && T1[T1[R1].left].element==T2[T2[R2].left].element)
return Isomorphic(T1[R1].left, T2[R2].left) && Isomorphic(T1[R1].right, T2[R2].right);
else return Isomorphic(T1[R1].left, T2[R2].right) && Isomorphic(T1[R1].right, T2[R2].left);
}
}
}