这道题我依然采用STL库的map，从而大幅减少了代码量

简单说一下思路，两棵树是否同构，只需比较俩树字母相同的结点是否同构，即是否左==左，右==右或者左==右，右==左。

1、条件准备

atree和btree是存两个数结点字母，第几个就存输入的第几个结点的字母。

map通过结点的字母作为键，从而找到两个子节点的信息

都要用char类型

#include <iostream>
#include <map>
using namespace std;

char atree[15], btree[15];
map<char, pair<char, char>> ma, mb;

主函数先是加快cin,cout

然后初始化两棵树，并保存结点个数，然后用solve函数进行处理

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int num;
    num = init(atree, ma);
    num = init(btree, mb);
    solve(num);

    return 0;
}

2、init函数

参数传递为要初始化的树的char数组和map，然后输入结点数。

循环输入第i个结点字母和其两子树的下标。

输入完后我们要把子树的下标转换成对应字母，

遍历结点数组，如果子节点不为‘-',则更新，将存的数字下标转为结点字母

int init(char *tree, map<char, pair<char, char>> &m)
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> tree[i];
        cin >> m[tree[i]].first >> m[tree[i]].second;
    }
    for (int i = 0; i < n; i++)
    {
        if (m[tree[i]].first != '-')
        {
            m[tree[i]].first = tree[m[tree[i]].first - '0'];
        }
        if (m[tree[i]].second != '-')
        {
            m[tree[i]].second = tree[m[tree[i]].second - '0'];
        }
    }
    return n;
}

3、judge函数

judge函数用来判断该节点俩树是否同构。

即左==左，右==右或者左==右，右==左。

bool judge(char c)
{
    if (ma[c].first == mb[c].first && ma[c].second == mb[c].second)
        return 1;
    if (ma[c].first == mb[c].second && ma[c].second == mb[c].first)
        return 1;
    return 0;
}

4、solve函数

遍历其中一棵树的结点，判断是否同构，不同构则输出No,

如果所有结点同构则输出Yes

void solve(int n)
{
    for (int i = 0; i < n; i++)
    {
        if (!judge(atree[i]))
        {
            cout << "No";
            return;
        }
    }
    cout << "Yes";
}

5、总结

这道题使用了map来减少了代码量，其实这一部分也可以用数组实现，因为树中的结点字母不重复，用字母的ACSII码作为下标也可以存储子树。

完整代码如下：

#include <iostream>
#include <map>
using namespace std;

char atree[15], btree[15];
map<char, pair<char, char>> ma, mb;

int init(char *tree, map<char, pair<char, char>> &m)
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> tree[i];
        cin >> m[tree[i]].first >> m[tree[i]].second;
    }
    for (int i = 0; i < n; i++)
    {
        if (m[tree[i]].first != '-')
        {
            m[tree[i]].first = tree[m[tree[i]].first - '0'];
        }
        if (m[tree[i]].second != '-')
        {
            m[tree[i]].second = tree[m[tree[i]].second - '0'];
        }
    }
    return n;
}

bool judge(char c)
{
    if (ma[c].first == mb[c].first && ma[c].second == mb[c].second)
        return 1;
    if (ma[c].first == mb[c].second && ma[c].second == mb[c].first)
        return 1;
    return 0;
}
void solve(int n)
{
    for (int i = 0; i < n; i++)
    {
        if (!judge(atree[i]))
        {
            cout << "No";
            return;
        }
    }
    cout << "Yes";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int num;
    num = init(atree, ma);
    num = init(btree, mb);
    solve(num);

    return 0;
}