03-树1 树的同构 (25 分)

03-树1 树的同构 (25 分)
给定两棵树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

题解：用一个check数组保存当前节点有无指向自己的节点，有就标记为1，没有呢被标记的就是根节点，因为没有节点会指向根节点。

具体解释都在代码里的注释了。

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
#define maxn 1000005
#define mod 7654321

struct Tree
{
    char Element;
    int Left;
    int Right;
}T1[20],T2[20];

int BuildTree(Tree *T)
{
    int n,Root=-1;
    int check[1000]={0};
    char l,r;
    cin>>n;
    if(n)
    {
        for(int i=0;i<n;i++)
            check[i]=0;
        for(int i=0;i<n;i++)
        {
            cin>>T[i].Element>>l>>r;
            if(l!='-')
                T[i].Left=l-'0',check[T[i].Left]=1;
            else
                T[i].Left=-1;
            if(r!='-')
                T[i].Right=r-'0',check[T[i].Right]=1;
            else
                T[i].Right=-1;
        }
        int i;
        for(i=0;i<n;i++)
            if(!check[i])
                break;
        Root=i;
    }
    return Root;
}
//-1代表空
int CHECK(int R1,int R2)
{
	//若两树都为空，则同构
    if(R1==-1&&R2==-1)
        return 1;
    //一个空一个不空，肯定不同构
    if((R1==-1&&R2!=-1)||(R1!=-1&&R2==-1))
        return 0;
    //若根节点的元素不同，肯定不同构
    if(T1[R1].Element!=T2[R2].Element)
        return 0;
    //若两树的左子树都为空，则递归的查看右子树
    if(T1[R1].Left==-1&&T2[R2].Left==-1)
        CHECK(T1[R1].Right,T2[R2].Right);
	
	//若两树左子树都不为空，则继续检查其对应的元素是否相同
    if (((T1[R1].Left!=-1)&&(T2[R2].Left!=-1))&&
        ((T1[T1[R1].Left].Element)==(T2[T2[R2].Left].Element)))
        //若一组元素相同，继续递归的解决左边的下一组，以及右面的每一组。
        return (CHECK(T1[R1].Left,T2[R2].Left)&&CHECK(T1[R1].Right,T2[R2].Right));
    //否则就是检查左右互换后是否同构。
    else
        return (CHECK(T1[R1].Left,T2[R2].Right)&&CHECK(T1[R1].Right, T2[R2].Left));
}

int main()
{
    int R1,R2;//存储根节点
    R1=BuildTree(T1);
    R2=BuildTree(T2);
    int result=CHECK(R1,R2);//从根节点开始找
    if(result)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;

    return 0;
}