【題目來源】
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) { //inorderif(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 0out:
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/
?
)
