分两步走 1：先建完全二叉树。2：再中序遍历填充。

// 两种算法

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int n;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {};
  TreeNode(int _val) :  val(_val), left(nullptr), right(nullptr) {};
  TreeNode(int _val, TreeNode* _left, TreeNode* _right) : val(_val), left(_left), right(_right) {};
  ~TreeNode() {};
};

// bfs 
TreeNode* buildTree(const int n) {
  // corner cae
  if (n <= 0) return nullptr;

  auto root = new TreeNode(0);
  queue<pair<TreeNode*, int>> q;
  q.emplace(root, 0);

  while (not q.empty()) {
    const auto [cur, idx] = q.front(); q.pop();

    int l_idx = idx << 1 | 1;
    if (l_idx >= n) break;
    cur->left = new TreeNode(l_idx);
    q.emplace(cur->left, l_idx);

    int r_idx = (idx << 1) + 2;
    if (r_idx >= n) break;
    cur->right = new TreeNode(r_idx);
    q.emplace(cur->right, r_idx);
  }

  return root;
}

// dfs 
TreeNode* buildTreeII(const int n, const int index) {
  // recursion exit condition
  if (index < 0 || index >= n) return nullptr;

  auto root   = new TreeNode(index);
  root->left  = buildTreeII(n, index << 1 | 1);
  root->right = buildTreeII(n, (index << 1) + 2);
  return root;
}

void fill(TreeNode* root, vector<int>& vals, int& index) {
  if (!root) return;
  fill(root->left, vals, index);
  root->val = vals[index++];
  fill(root->right, vals, index);
}

vector<int> levelOrder(TreeNode* root) {
  // corner case
  if (!root) return {};

  queue<TreeNode*> q{{root}};

  vector<int> ans;
  while (not q.empty()) {
    const auto cur = q.front(); q.pop();
    ans.emplace_back(cur->val);
    if (cur->left)  q.emplace(cur->left);
    if (cur->right) q.emplace(cur->right);
  }

  return ans;
}

void printAns(vector<int>& ans) {
  for (int i = 0; i < ans.size(); ++i) {
    printf("%d", ans[i]);
    if (i < ans.size() - 1) putchar(' ');
  }
  putchar('\n');
}

// ---- debug helper function begin ---- 
void preOrder(TreeNode* root) {
  if (!root) return;
  printf("%d ", root->val);
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(TreeNode* root) {
  if (!root) return;
  inOrder(root->left);
  printf("%d ", root->val);
  inOrder(root->right);
}
// ---- debug helper function end ---- 

int main(void) {
  cin >> n;
  vector<int> vals(n);
  for (int i = 0 ; i < n; ++i) cin >> vals[i];
  sort(begin(vals), end(vals));

  auto root = buildTreeII(n, 0);
  int index = 0;
  fill(root, vals, index);

  auto ans = levelOrder(root);
  printAns(ans);
}