【题目来源】
https://www.acwing.com/problem/content/1552/
【题目描述】
二叉搜索树 (BST) 递归定义为具有以下属性的二叉树：
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
（2）若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
（3）它的左、右子树也分别为二叉搜索树
完全二叉树 (CBT) 定义为除最深层外的其他层的结点数都达到最大个数，最深层的所有结点都连续集中在最左边的二叉树。
现在，给定 N 个不同非负整数，表示 N 个结点的权值，用这 N 个结点可以构成唯一的完全二叉搜索树。
请你输出该完全二叉搜索树的层序遍历。
【输入格式】
第一行包含整数 N，表示结点个数。
第二行包含 N 个不同非负整数，表示每个结点的权值。
【输出格式】
共一行，输出给定完全二叉搜索树的层序遍历序列。
【数据范围】
1≤N≤1000,
结点权值不超过 2000。
【输入样例】
10
1 2 3 4 5 6 7 8 9 0
【输出样例】
6 3 8 1 5 7 9 0 2 4
【算法分析】
● 二叉搜索树（BST，Binary Search Tree）
二叉搜索树的形态与给定的序列值及顺序相关。也就是说，即便序列的值相同，但依据“左小右大”的原则，不同的次序也会生成不同形态的二叉搜索树。
（45，24，53，12，37，93） （12，24，37，45，53，93）
● 完全二叉树
如果在一棵具有n个结点的二叉树中，它的逻辑结构与满二叉树的前n个结点的逻辑结构相同，则称这样的二叉树为完全二叉树。显然，在完全二叉树中，结点 u 的左孩子为 2*u，右孩子为 2*u+1。
● 二叉搜索树具有一个重要的性质，即它的中序遍历序列是递增的。那又如何据此性质，输出二叉搜索树的层序遍历序列呢？
对二叉搜索树的结点值进行递增排序，然后执行类似于中序遍历的 dfs 操作，并在 dfs 过程中将对应的二叉搜索树结点值存入一个中序数组中，之后输出中序数组便可得到所求的二叉搜索树的层序遍历序列。
【算法代码】
#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;
int a[maxn],in[maxn];
int n,idx;
void dfs(int u) { //inorder
if(u*2<=n) dfs(u*2);
in[u]=a[idx++];
if(u*2+1<=n) dfs(u*2+1);
}
int main() {
cin>>n;
for(int i=0; i<n; i++) cin>>a[i];
sort(a,a+n);
dfs(1); //is 1,not 0. Otherwise,dfs can't run.
for(int i=1; i<=n; i++) cout<<in[i]<<" ";
return 0;
}
/*
in:
10
1 2 3 4 5 6 7 8 9 0
out:
6 3 8 1 5 7 9 0 2 4
*/
【参考文献】
https://blog.csdn.net/justinzengTM/article/details/81459482
https://www.acwing.com/solution/content/11649/
https://www.acwing.com/solution/content/97469/
