PTA浙江大学数据结构习题——第三周

树的同构

#include 
#include 

using namespace std;

const int N = 15;

struct TreeNode
{
    char e;
    int left, right;
} T1[N], T2[N];

bool st[N];

int BuildTree(struct TreeNode t[])
{
    int n;
    cin >> n;
    memset(st, false, sizeof st);
    
    char a, b, c;
    for (int i = 0; i < n; i ++)
    {
        cin >> a >> b >> c;
        t[i].e = a;
        if (b != '-')
        {
            t[i].left = b - '0';
            st[b - '0'] = true;
        }
        else    t[i].left = -1;
        
        if (c != '-')   
        {
            t[i].right = c - '0';
            st[c - '0'] = true;
        }
        else    t[i].right = -1;
    }
    
    // 寻根
    int root = -1;
    for (int i = 0; i < n; i ++)
        if (!st[i])
        {
            root = i;
            break;
        }
    return root;
}

bool check(int r1, int r2)
{
    if ((r1 == -1) && (r2 == -1))   return true;    // 两个节点为空
    
    if (((r1 == -1) && (r2 != -1)) || ((r1 != -1) && (r2 == -1)))   return false;   // 一个节点空，另一个不空
    if (T1[r1].e != T2[r2].e)   return false;       // 两个节点不相同
    
    if ((T1[r1].left == -1) && (T2[r2].left == -1)) return check(T1[r1].right, T2[r2].right);   // 两个节点的左子树都为空
    
    if ((T1[r1].left != -1) && (T2[r2].left != -1) && (T1[T1[r1].left].e == T2[T2[r2].left].e)) // 两个节点的左子树相同
        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);
    
    if (check(r1, r2))  puts("Yes");
    else    puts("No");
    
    return 0;
}