博客

给定两棵树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

思路


这里的树的同构是指一棵树使某些节点左右子树交换后能成为另一棵树，则这两棵树同构，那么这里的树是指二叉树，根据要求，只要两棵树中值相同的节点应该有相同的左右子树，只是左右子树的位置可以相反，或者值相同的节点有相同的父节点。这里我们用第一种方法判断。


代码

#include <iostream>
#include <map>
using namespace std;
struct Node {
    char Data;
    char left;
    char right;
}N1[10], N2[10];
int main()
{
    int n;
    cin >> n;
    map<char, pair<char, char>> mp;
    for (int i = 0; i < n; i++)
        cin >> N1[i].Data >> N1[i].left >> N1[i].right;
    for (int i = 0; i < n; i++) {
        N1[i].left = N1[i].left == '-' ? '-' : N1[N1[i].left - '0'].Data;
        N1[i].right = N1[i].right == '-' ?  '-' : N1[N1[i].right - '0'].Data;
        mp[N1[i].Data] = pair<char, char>(N1[i].left, N1[i].right);
    }
    cin >> n1;
    if(n1 != n){  //这里其实不判断样例也过了
        printf("No");
        return 0;
    } 
    for (int i = 0; i < n; i++)
        cin >> N2[i].Data >> N2[i].left >> N2[i].right;
    for (int i = 0; i < n; i++) {
        N2[i].left = N2[i].left == '-' ? '-' : N2[N2[i].left - '0'].Data;
        N2[i].right = N2[i].right == '-' ? '-' : N2[N2[i].right - '0'].Data;
        if (!(mp[N2[i].Data].first == N2[i].left && mp[N2[i].Data].second == N2[i].right
            || mp[N2[i].Data].first == N2[i].right && mp[N2[i].Data].second == N2[i].left)) {
            printf("No");
            return 0;
        }
    }
    printf("Yes");
    return 0;
}