拼题A 树的同构

拼题A 树的同构

题目描述：
给定两棵树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

根据题意很容易知道判断两棵树是否同构只需判断这两棵树同一结点的左右子树是否相同（顺序可以颠倒），题目所给的结点的顺序不同，所以先排个序再操作。

处理特殊字符 ‘ - ’：如果不考虑特殊字符的话，就可以直接判断左右子树了，然后我输出了一下‘ - ’ - ‘ 0 ’的结果发现为-3，那当我们每次将结点的左右子树转换为整型时，就特判一下，如果为负，就让左/右的数值为一个不可能出现的数10（题目说了N <= 10），这里我开了两个数组分别存两棵树所对应的下标的数据，然后让两个数组[10]都为’ - '，这样就可以正常判断了。

上代码：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct Tree
{
    char data;
    char left_tree, right_tree;
    int id;
};
Tree t1[20], t2[20];
char a[20], b[20];
int n;

bool cmp(Tree a, Tree b)
{
    return a.data < b.data;
}

bool judge_tg()
{
    for(int i = 0; i < n; i++)
    {
        if(t1[i].data != t2[i].data) // 既然排过序了，那么如果同构的话每个结点的数据应该都相同，不同则不可能同构
            return false;
        int l1, l2, r1, r2;
        
        l1 = t1[i].left_tree - '0';
        if(l1 < 0)
            l1 = 10;
            
        l2 = t2[i].left_tree - '0';
        if(l2 < 0)
            l2 = 10;
            
        r1 = t1[i].right_tree - '0';
        if(r1 < 0)
            r1 = 10;
            
        r2 = t2[i].right_tree - '0';
        if(r2 < 0)
            r2 = 10;
            
        if( !( (a[l1] == b[l2] && a[r1] == b[r2] ) || ( a[l1] == b[r2] && a[r1] == b[l2]) ) )
            return false;
    }
    return true;
}

int main()
{
    //printf("%d\n", '-'-'0'); // -3
    a[10] = '-';
    b[10] = '-';
    
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        getchar();
        scanf("%c %c %c", &t1[i].data, &t1[i].left_tree, &t1[i].right_tree);
        t1[i].id = i;
        a[i] = t1[i].data;
    }
    sort(t1, t1 + n, cmp);
    
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        getchar();
        scanf("%c %c %c", &t2[i].data, &t2[i].left_tree, &t2[i].right_tree);
        t2[i].id = i;
        b[i] = t2[i].data;
    }
    sort(t2, t2 + n, cmp);
    
    if(judge_tg())
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}