#include<bits/stdc++.h>
using namespace std;
vector<int>temp;
struct node{
int data;
node*l,*r;
};
int top,ttop;
int f;
void Swap(node *root){
if(root){
Swap(root->l);
Swap(root->r);
swap(root->l,root->r);
}
}
node* build(node* root,int num){
if(root==NULL){
node*p = new node;
p->data = num;
p->l = NULL;
p->r = NULL;
return p;
}
if(num<root->data){
root->l = build(root->l,num);
}
else{
root->r = build(root->r,num);
}
return root;
}
void xian(node*root){
if(root&&f){
if(root->data!=temp[top++])f =0;
xian(root->l);
xian(root->r);
}
}
void hou(node*root){
if(root){
hou(root->l);
hou(root->r);
if(ttop)ttop =0;
else printf(" ");
printf("%d",root->data);
}
}
int main(int argc, char* argv[])
{
int n;
cin>>n;
node *root = NULL;
for(int i=1;i<=n;i++){
int num;
cin>>num;
temp.push_back(num);
root = build(root,num);
}
f = 1;
top = 0;
xian(root);
if(!f){
f = 1;
top =0;
Swap(root);
xian(root);
}
if(f){
printf("YES\n");
ttop =1;
hou(root);
}
else printf("NO\n");
return 0;
}数组模拟：17分
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int a[2000000],top;
int b[2000000];
vector<int>ans;
void Insert(int root,int num)
{
if(a[root]==-1)
{
a[root] = num;
return;
}
if(num<a[root])
Insert(root*2,num);
else
{
Insert(root*2+1,num);
}
}
//void cc(int root){
//
// queue<int>o;
// o.push(root);
// while(!o.empty()){
//
// int y = o.front();
// o.pop();
// cout<<a[y]<<" ";
// if(a[y*2]!=-1)
// o.push(y*2);
// if(a[y*2+1]!=-1)
// o.push(y*2+1);
// }
//}
void cc(int y)
{
if(a[y]==-1)return;
ans.push_back(a[y]);
if(a[y*2]!=-1)
cc(y*2);
if(a[y*2+1]!=-1)
cc(y*2+1);
}
void S(int y)
{
if(a[y]==-1)return;
S(y*2);
S(y*2+1);
swap(a[y*2],a[y*2+1]);
}
void hou(int y)
{
if(a[y]==-1)return;
if(a[y*2]!=-1)
hou(y*2);
if(a[y*2+1]!=-1)
hou(y*2+1);
if(top)top =0;
else printf(" ");
cout<<a[y];
}
int main()
{
int n;
cin>>n;
memset(a,-1,sizeof a);
memset(b,-1,sizeof b);
int f =0;
for(int i=1; i<=n; i++)
{
int num;
cin>>num;
b[i-1] = num;
Insert(1,num);
}
cc(1);
int u = 1;
for(int i=0;i<n;i++){
if(ans[i]!=b[i]){
u =0;
}
}
if(u==1)f = 1;
if(!f){
S(1);
ans.clear();
cc(1);
u = 1;
for(int i=0;i<n;i++){
if(ans[i]!=b[i]){
u =0;
}
}
if(u==1)f = 1;
}
// printf("\n");
if(f)
{
printf("YES\n");
top = 1;
hou(1);
}
else printf("NO\n");
// int m;
// cin>>m;
// for(int I=1;I<=m;I++){
//
// int a1;
// string ta;
// cin>>a1>>t1;
// if(t1=="is"){
//
// cin>>t1>>t1;
// if(t1=="root"){
//
// if(mp)
// }
// }
// }
return 0;
}