给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。
图1
图2
现给定两棵树，请你判断它们是否是同构的。
输入样例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
#include<iostream>
using namespace std;
#define MAXSIZE 100
typedef char ElementType;//char
struct TreeNode{
ElementType data;
int left;
int right;
}T1[MAXSIZE],T2[MAXSIZE]; //T1,T2数组全局声明了，全局可用
int CreateTree(TreeNode T[]){ //从根节点开始标下标，根节点标0，不存在的节点的标-1，就是Null,最后返回根节点的下标,
int n; cin>>n;
int check[MAXSIZE]={0};//无父节点指向它
char ldata,rdata;
int root=-1;//防止当n=0时，for循环不执行，root没有值
for(int i=0;i<n;i++){
cin>>T[i].data>>ldata>>rdata;//这3个都是char类型输进来的，后两个char是因为如果无对应的数据，就输'-'
if(ldata!='-'){
T[i].left=ldata-'0';
check[ T[i].left ]=1;
}else
T[i].left=-1;
if(rdata!='-'){
T[i].right=rdata-'0';
check[ T[i].right ]=1;
}else
T[i].right=-1;
}
for(int i=0;i<n;i++){
if( !check[i] ){
root=i;
break;
}
}
return root;
}
bool IsTonggou(int root1,int root2){
if(root1==-1 && root2==-1) return true;
if( (root1 == -1)&&(root2 != -1) || (root1 != -1)&&(root2 == -1) ) return false;//不能写成root1==-1 || root2==-1 ，因为这句包含了上句 root1==-1 && root2==-1 的情况
if(T1[root1].data != T2[root2].data) return false;
if(T1[root1].left==-1 && T2[root2].left==-1) return IsTonggou(T1[root1].right,T2[root2].right);
if( (T1[root1].left!=-1 && T2[root2].left!=-1) && (T1[T1[root1].left].data==T2[T2[root2].left].data) )
return ( IsTonggou(T1[root1].left,T2[root2].left) && IsTonggou(T1[root1].right,T2[root2].right) );
else return ( IsTonggou(T1[root1].left,T2[root2].right) && IsTonggou(T1[root1].right,T2[root2].left) );
}
int main(){
//freopen("input.txt","r",stdin);
int root1,root2;
root1= CreateTree(T1);
root2= CreateTree(T2);
//cout<<root1<<" "<<root2<<endl;return 0;
if( IsTonggou(root1,root2) ) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
