2019冬季PAT甲級第四題
6497 ワード
1 #define HAVE_STRUCT_TIMESPEC
2 #include
3 using namespace std;
4 typedef struct node{
5 int data;
6 node *lchild,*rchild;
7 }tree;
8 int a[37];
9 tree *build(int l,int r){
10 if(l>r)
11 return NULL;
12 int mn=1e9+7,pos=0;
13 for(int i=l;i<=r;++i)
14 if(a[i]<mn)
15 mn=a[i],pos=i;
16 tree *temp=new tree();
17 temp->data=mn;
18 temp->lchild=build(l,pos-1);
19 temp->rchild=build(pos+1,r);
20 return temp;
21 }
22 int main(){
23 ios::sync_with_stdio(false);
24 cin.tie(NULL);
25 cout.tie(NULL);
26 int n;
27 cin>>n;
28 for(int i=1;i<=n;++i)
29 cin>>a[i];
30 tree *temp=build(1,n);
31 queueq;
32 q.push(temp);
33 int ans[37]={};
34 int cnt=0;
35 while(!q.empty()){
36 tree *now=q.front();
37 q.pop();
38 ans[++cnt]=now->data;
39 if(now->lchild)
40 q.push(now->lchild);
41 if(now->rchild)
42 q.push(now->rchild);
43 }
44 for(int i=1;i<=cnt;++i){
45 if(i>1)
46 cout<<" ";
47 cout<<ans[i];
48 }
49 return 0;
50 }