L2-004. 这是二叉搜索树吗？
题目链接：https://www.patest.cn/contests/gplt/L2-004
这题我的方法是先递归判定是不是二叉搜索树（镜像），再建树输出。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
bool isST(int a[],int l,int r){
if(l>=r)return ;
int key=r;
for(int i=l+;i<=r;++i){
if(a[l]<=a[i]){
key=i;
break;
}
}
for(int i=key+;i<=r;++i)
if(a[l]>a[i])return ;
return isST(a,l+,key-)&&isST(a,key,r);
}
bool isMirST(int a[],int l,int r){
if(l>=r)return ;
int key=r;
for(int i=l+;i<=r;++i){
if(a[l]>a[i]){
key=i;
break;
}
}
for(int i=key+;i<=r;++i)
if(a[l]<=a[i])return ;
return isMirST(a,l+,key-)&&isMirST(a,key,r);
}
struct node{
int vul;
node *l,*r;
};
node *T=NULL;
node* st(node *t,int key){
if(t==NULL){
node *temp=(node*)malloc(sizeof(node));
temp->vul=key;
temp->l=NULL;
temp->r=NULL;
return temp;
}
if(key>=t->vul)t->r=st(t->r,key);
else t->l=st(t->l,key);
return t;
}
node* Mirst(node *t,int key){
if(t==NULL){
node *temp=(node*)malloc(sizeof(node));
temp->vul=key;
temp->l=NULL;
temp->r=NULL;
return temp;
}
if(key<t->vul)t->r=Mirst(t->r,key);
else t->l=Mirst(t->l,key);
return t;
}
void printT(node *t){
if(t==NULL)return;
printT(t->l);
printT(t->r);
if(t!=T)printf("%d ",t->vul);
}
int main(void){
freopen("in.txt","r",stdin);
int a[];
memset(a,,sizeof(a));
int n;
scanf("%d",&n);
if(n==){
printf("YES\n");
return ;
}
for(int i=;i<n;++i)
scanf("%d",&a[i]);
bool flag1=isST(a,,n-);
bool flag2=isMirST(a,,n-);
if(!(flag1||flag2)){
printf("NO\n");
return ;
}
else if(flag1)for(int i=;i<n;++i)T=st(T,a[i]);
else if(flag2)for(int i=;i<n;++i)T=Mirst(T,a[i]);
printf("YES\n");
printT(T);
printf("%d",T->vul);
printf("\n");
return ;
}
如有更好的方法，希望不吝赐教!!