PTA 7-3 树的同构

题干大致的意思是：给定两颗二叉树的信息，判断他们是否同构（其中一棵树将左右子树经过若干次调换后得到另一颗树）

对于二叉树的问题一般使用递归方法解决。

1.创建二叉树：

首先需要将输入转化为熟悉的结构体指针BinTree的形式，写一个CreatTree函数来实现这个转化；

这里需要特别注意查找根节点的位置，不要直接根据输入案例1想当然地将第一个输入地值当作根节点

2.判断是否是同构：

这里采用地是dfs(深度优先遍历)地办法，如果这两棵树是同构地，那么这棵树的左子树一定等于另一棵树相同位置的节点的左子树或者右子树，反之，如果不相等，那么这两棵树一定不是同构的.

#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
    char data;
    Node* left;
    Node* right;
}*BinTree;
//判断是否是同构
bool judge(BinTree a,BinTree b){
    if(a == nullptr || b==nullptr) return a==b;//a和b有空节点时
    if(a->data == b->data){
        return (judge(a->left,b->left) && judge(a->right,b->right))
            || (judge(a->left,b->right) && judge(a->right,b->left));
    }
    return false;//如果ab元素不相等直接返回false.
}
//将输入转化为二叉树
BinTree CreatTree(vector<Node>&t){
    int n;
    cin>>n;
    if(n==0) return nullptr;//n为0时返回空树.
    t.resize(n);
    vector<bool> hasParent(n,false);//标识数组，用来判断是否有父节点，用来找根节点
    for(int i=0;i<n;i++){
        char c,a,b;
        cin>>c>>a>>b;
        t[i].data = c;
        if(a!='-'){
            t[i].left = &t[a-'0'];//因为这里的n小于等于10，可以直接减
            hasParent[a-'0']= true;
        }else{
            t[i].left = nullptr;
        }
        if(b !='-'){
            t[i].right = &t[b-'0'];
                hasParent[b-'0']= true;
        }else{
            t[i].right = nullptr;
        }
    }
    int headpos;//根节点对应的数组下标
    for(int i=0;i<n;i++){
        if(!hasParent[i]){//当标识数组为false时，该下标即为头节点的位置
            headpos =i;
            break;
        }
    }
    return &t[headpos];//返回头节点的地址
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<Node>v1,v2;
    BinTree t1 = CreatTree(v1);//输入的第一颗树
    BinTree t2 = CreatTree(v2);//输入的第二棵树
    if(judge(t1,t2)){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
    
}