Complete binary search tree (30 points)

A sequence of nonnegative integers without repetition , It must correspond to a unique binary search tree with the shape of a complete binary tree . This problem requires you to output the sequence traversal sequence of this tree .

Input format ：

First, the first line gives a positive integer  N（≤1000）, Then the second line gives  N  A non repeating nonnegative integer . Numbers are separated by spaces , All figures do not exceed 2000.

Output format ：

Output the sequence traversal sequence of the tree in one line . Between the numbers 1 Space separation , There must be no extra space at the beginning and end of the line .

sample input ：

10
1 2 3 4 5 6 7 8 9 0

sample output ：

6 3 8 1 5 7 9 0 2 4

#include<bits/stdc++.h>
using namespace std;
int g[1010],in[1010];
int id,n;
void pre(int root){
    if(root>n)return;
    pre(root*2);
   in[root]=g[id++];
    pre(root*2+1);

}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>g[i];
    sort(g,g+n);
    pre(1);
    cout<<in[1];
    for(int i=2;i<=n;i++)cout<<" "<<in[i];
}