https://pintia.cn/problem-sets/994805046380707840/problems/99480507097191219
L2-004 这是二叉搜索树吗? (25 分)
作者: 陈越
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
#include<bits/stdc++.h> #define ll long long int #define mod 998244353 using namespace std; int a[2000]; struct node*root = NULL; struct node { int data; struct node*l; struct node*r; }; int check1(int l,int r) { if(l>=r)return 1; int key = r; for(int i=l+1; i<=r; i++) { if(a[l]<=a[i]) { key = i; break; } } for(int i=key+1; i<=r; i++) { if(a[l]>a[i])return 0; } return check1(l+1,key-1)&&check1(key,r); } int check2(int l,int r) { if(l>=r)return 1; int key = r; for(int i=l+1; i<=r; i++) { if(a[l]>=a[i]) { key = i; break; } } for(int i=key+1; i<=r; i++) if(a[l]<a[i]) return 0 ; return check2(l+1,key-1)&&check2(key,r); } struct node* build(struct node*t,int key) { if(t==NULL) { node* p = new node; p->data = key; p->l = NULL; p->r = NULL; return p; } if(key>=t->data) t->r = build(t->r,key); else t->l = build(t->l,key); return t; } struct node* build2(struct node*t,int key) { if(t==NULL) { node* p = new node; p->data = key; p->l = NULL; p->r = NULL; return p; } if(key<t->data) t->r = build2(t->r,key); else t->l = build2(t->l,key); return t; } void print(struct node*t) { if(!t) return ; print(t->l); print(t->r); if(t!=root) printf("%d ",t->data); } int main() { // ios::sync_with_stdio(false); int n; cin>>n; for(int i=0; i<n; i++) { cin>>a[i]; } int flag1 = check1(0,n-1); int flag2 = check2(0,n-1); if(!flag1&&!flag2) { printf("NO\n"); return 0; } if(!flag1) for(int i=0; i<n; i++) root = build2(root,a[i]); else for(int i=0; i<n; i++) root = build(root,a[i]); printf("YES\n"); print(root); printf("%d\n",root->data); return 0; }