【题解】二叉排序树的同构

题意

给你一棵二叉排序树，由于一棵二叉排序所构造其的序列是不唯一的，求有多少个序列可以构造出该树。

题解

首先我们可以看到题中的的的大小比较少，所以我们可以考虑通过遍历的全排列的方式来找到所有可能的同构序列，每次对遍历序列构建一棵二叉排序树，判断两棵二叉树是否同构用判断对应节点是否相等即可。
也可以通过从二叉排序树的最小字典序序列到啊最大字典序序列进行剪枝。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e5+5;
struct BiTree
{
    int v;
    BiTree *lchild;
    BiTree *rchild;
};
int a[N];
void Insert(BiTree *&T,int v)
{
    if(T==NULL)
    {
        T=new BiTree;
        T->v=v;
        T->lchild=NULL;
        T->rchild=NULL;
        return;
    }
    if(T->v>v)
        Insert(T->lchild,v);
    else
        Insert(T->rchild,v);
}
bool flag=true;
bool dfs(BiTree *T1,BiTree * T2)
{
    if(T1!=NULL&&T2!=NULL)
    {
        if(T1->v!=T2->v)
            return false;
        return dfs(T1->lchild,T2->lchild)&&dfs(T1->rchild,T2->rchild);
    }
    else
    {
        if(T1==NULL&&T2==NULL)
            return true;
        else
            return false;
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    BiTree *T1=NULL;
    for(int i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
        Insert(T1,a[i]);
    }
    int b[n];
    for(int i=0;i<n;i++)
        b[i]=i+1;
    int ans=0;
    do
    {
        BiTree *T2=NULL;
        for(int i=0;i<n;i++)
            Insert(T2,b[i]);
        if(dfs(T1,T2))
        {
            ans++;
        }
    }while(next_permutation(b,b+n));
    printf("%d\n",ans);
}