给定两棵树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
主要思路：
1、合理建树并寻找根结点
2、递归时的树的同构与不同构的多种情形的考虑（见代码注释）
不足之处：
1、递归时直接在vector上判断孩子结点的情况导致代码可读性变差
#include <iostream>#include <vector>using namespace std;#define Max_Node 11#define END -1typedef struct node{ char value; int left; int right;}Node;void CreateTree(vector<Node>& Tree,int N)//获取树的输入，并将输入的字符合理转化成整型数字{ char value,left,right; for (int i=0; i<N; ++i) { cin>>value>>left>>right; Tree[i].value=value; if (left=='-') { Tree[i].left=END; }else { Tree[i].left=left-'0'; } if (right=='-') { Tree[i].right=END; }else { Tree[i].right=right-'0'; } }}int FindTreeRoot(vector<Node>& Tree,int N)//寻找树的树根（树根没有其它的结点指向它）{ int Flag[Max_Node]; for (int i=0; i<N; ++i) { Flag[i]=0; } for (int i=0; i<N; ++i) { if (Tree[i].left!=END) { Flag[Tree[i].left]=1; } if (Tree[i].right!=END) { Flag[Tree[i].right]=1; } } int k; for (k=0; k<N; ++k) { if (Flag[k]==0) { break; } } return k;}bool IsOmorphic(int Root1,int Root2,vector<Node>& Tree1,vector<Node>& Tree2)//递归判断两树是否同构{ if (Tree1[Root1].value==Tree2[Root2].value) { //两结点相等，并都是叶子结点 if (Tree1[Root1].left==END && Tree1[Root1].right==END && Tree2[Root2].left==END && Tree2[Root2].right==END) { return true; } //以下四种情况都是，两个结点都是有一个孩子为空，另一个子树不空且这两个孩子相等的情形 if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].left].value && Tree1[Root1].right==END && Tree2[Root2].right==END) { return IsOmorphic(Tree1[Root1].left, Tree2[Root2].left, Tree1, Tree2); } if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].right].value && Tree1[Root1].right==END && Tree2[Root2].left==END) { return IsOmorphic(Tree1[Root1].left, Tree2[Root2].right, Tree1, Tree2); } if (Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].left].value && Tree1[Root1].left==END && Tree2[Root2].right==END) { return IsOmorphic(Tree1[Root1].right, Tree2[Root2].left, Tree1, Tree2); } if (Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].right].value && Tree1[Root1].left==END && Tree2[Root2].left==END) { return IsOmorphic(Tree1[Root1].right, Tree2[Root2].right, Tree1, Tree2); } //以下两种情形，两个结点的孩子都相等 if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].left].value && Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].right].value) { return (IsOmorphic(Tree1[Root1].left, Tree2[Root2].left, Tree1, Tree2))&&(IsOmorphic(Tree1[Root1].right, Tree2[Root2].right, Tree1, Tree2)); } if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].right].value && Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].left].value) { return (IsOmorphic(Tree1[Root1].left, Tree2[Root2].right, Tree1, Tree2))&&(IsOmorphic(Tree1[Root1].right, Tree2[Root2].left, Tree1, Tree2)); } } //不符合以上7种情况的其它情况都说明这两棵树不同构 return false;}int main(int argc, const char * argv[]){ //Input int N1=0; cin>>N1; vector<Node> Tree1(Max_Node); CreateTree(Tree1,N1); int N2=0; cin>>N2; vector<Node> Tree2(Max_Node); CreateTree(Tree2,N2); if (N1!=N2) { cout<<"No"; }else { if (N1==0) { cout<<"Yes"; }else { //Build Tree int root1=FindTreeRoot(Tree1,N1); int root2=FindTreeRoot(Tree2,N2); //Judge if (IsOmorphic(root1, root2, Tree1, Tree2)) { cout<<"Yes"; }else { cout<<"No"; } } } return 0;}