03-树1 树的同构

题意

给你两棵树，判断这两棵树是否同构。

解题思路

树同构说明树的大小完全相同，因此我们可以递归遍历树的时候，对于树A，B，我们访问A的左子树时，我们也可以同时访问B的右子树，同理访问A的右子树时，我们也可以同时访问B的左子树。

查找树根：我们对所有结点的左右子树已经出现的下标做标记，如果某个下标没有出现，那么该下标对应的结点是树根。

参考代码

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
#define MAXN 15
struct Node{
    int l,r;
    char D;
}tree[2][MAXN];
bool used[MAXN];
int build(int n,int k){
    char D,l,r;
    memset(used,false,sizeof(used));
    for (int i=0;i<n;i++){
        cin>>D>>l>>r;
        tree[k][i].D=D;
        if (l=='-') 
            tree[k][i].l=-1;
        else{ 
            tree[k][i].l=l-'0';
            used[l-'0']=true;
        }
        if (r=='-') 
            tree[k][i].r=-1;
        else{ 
            tree[k][i].r=r-'0';
            used[r-'0']=true;
        }
    }
    int ans=0;
    for (int i=0;i<n;i++)
        if (used[i]==false)
            ans=i;
    return ans;
}
bool judge(int i,int j){
    if (tree[0][i].D==tree[1][j].D){
        if (tree[0][i].l==tree[1][j].r && tree[0][i].l==-1) return true;
        if (tree[0][i].r==tree[1][j].l && tree[0][i].r==-1) return true;

        if (tree[0][i].l!=tree[1][j].r && tree[0][i].l==-1) return false;
        if (tree[0][i].r!=tree[1][j].l && tree[0][i].r==-1) return false;

        if (tree[0][i].l!=tree[1][j].r && tree[1][j].r==-1) return false;
        if (tree[0][i].r!=tree[1][j].l && tree[1][j].l==-1) return false;

        if (judge(tree[0][i].l,tree[1][j].r)==true) return true;
        else return false;
        if (judge(tree[0][i].r,tree[1][j].l)==true) return true;
        else return false;
    }
    return false;
}
int main(){
    int n,m;
    scanf("%d",&n);
    int i=build(n,0);
    scanf("%d",&m);
    int j=build(m,1);
    if (n==0 && m==0) printf("Yes\n");
    else if (n==0 && m) printf("No\n");
    else if (m & n==0) printf("No\n");
    else if (judge(i,j)==true) printf("Yes\n");
    else printf("No\n");
    return 0;
}