Complete binary search tree (30 points)

Insert a series of given numbers into a binary search tree which is initially empty （ It is defined as the left subtree with large key value , The key value of the right subtree is small ）, You need to determine whether the final tree is a complete binary tree , And the result of sequence traversal is given .

Input format ：

The first line of input gives no more than one 20 The positive integer N; The second line gives N Two different positive integers , Separated by spaces .

Output format ：

Will input N Insert an initially empty binary search tree in the order of positive integers . Output the sequence traversal result of the result tree in the first line , Between the numbers 1 Space separation , There must be no extra Spaces at the beginning or end of the line . The second line outputs YES, If the tree is a complete binary tree ; Otherwise output NO.

sample input 1：

9
38 45 42 24 58 30 67 12 51

sample output 1：

38 45 24 58 42 30 12 67 51
YES

sample input 2：

8
38 24 12 45 58 67 42 51

sample output 2：

38 45 24 58 42 12 67 51
NO

#include<bits/stdc++.h>
using namespace std;
vector<int> level(100010, -1);
int n, t, flag, st, cnt;
void build(int val, int root){
    if(val > level[root]){
        if(level[2 * root + 1] != -1)   build(val, 2 * root + 1);
        else    level[2 * root + 1] = val;
    }  
    else   if(val < level[root]){
        if(level[2 * root + 2] != -1)   build(val, 2 * root + 2);
        else    level[2 * root + 2] = val;
    }
}
int main(){
    cin >> n >> t, level[0] = t;
    for(int i = 1;i < n;i++)    cin >> t, build(t, 0);
    for(int i = 0;i < 100010;i++){
        if(level[i] != -1){
            if(flag++)  cout << " ";
            cout << level[i];
            cnt++;
        }else{
            if(cnt < n) st = 1;
        }
    }
    if(st)  cout << endl << "NO";
    else    cout << endl << "YES";
}