2020年団体プログラム設計天梯試合-総決勝L 2-3完全二叉樹の層序遍歴
L 2-3完全二叉木の層順遍歴(25分)
各レイヤのノード数が最大値に達すると、このツリーは完全なツリーになります.深さDの場合、N個のノードがあるツリーは、同じ深さの完璧なツリーの層順に遍歴する前のN個のノードに対応するツリーが完全なツリーである.
完全な二叉木の後序遍歴を与えて、この木の層序遍歴結果を与えてください.
入力形式:
入力は、1行目に正の整数N(≦30)、すなわち、ツリー内のノード数を与える.2行目は、N個の100を超えない正の整数である後系列遍歴シーケンスを与える.同じ行のすべての数字はスペースで区切られています.
出力フォーマット:
ツリーのレイヤシーケンスループシーケンスを1行に出力します.すべての数字は1つのスペースで区切られており、行の先頭と末尾に余分なスペースがないようにしてください.
サンプルを入力:
8
91 71 2 34 10 15 55 18
出力サンプル:
18 34 55 71 2 10 15 91
作成者
陳越
たんい
浙江大学
コード長制限
16 KB
時間の制限
400 ms
メモリ制限
64 MB
問題解
解法1
時計を打つ(10まで打つと22点になる)
#include
using namespace std;
int main() {
int n,a[102],pos[102];
cin >> n;
for(int i=1; i<=n; i++) {
cin >> a[i];
}
if(n == 1) {
int tmp[]={
1};
for(int i=0; i<n; i++) {
pos[i] = tmp[i];
}
} else if(n == 2) {
int tmp[]={
2,1};
for(int i=0; i<n; i++) {
pos[i] = tmp[i];
}
} else if(n == 3) {
int tmp[]={
3,1,2};
for(int i=0; i<n; i++) {
pos[i] = tmp[i];
}
} else if(n == 4) {
int tmp[]={
4,2,3,1};
for(int i=0; i<n; i++) {
pos[i] = tmp[i];
}
} else if(n == 5) {
int tmp[]={
5,3,4,1,2};
for(int i=0; i<n; i++) {
pos[i] = tmp[i];
}
} else if(n == 6) {
int tmp[]={
6,3,5,1,2,4};
for(int i=0; i<n; i++) {
pos[i] = tmp[i];
}
} else if(n == 7) {
int tmp[]={
7,3,6,1,2,4,5};
for(int i=0; i<n; i++) {
pos[i] = tmp[i];
}
} else if(n == 8) {
int tmp[]={
8,4,7,2,3,5,6,1};
for(int i=0; i<n; i++) {
pos[i] = tmp[i];
}
} else if(n == 9) {
int tmp[]={
9,5,8,3,4,6,7,1,2};
for(int i=0; i<n; i++) {
pos[i] = tmp[i];
}
} else if(n == 10) {
int tmp[]={
10,6,9,3,5,7,8,1,2,4};
for(int i=0; i<n; i++) {
pos[i] = tmp[i];
}
}
/*......*/
for(int i=0; i<n; i++) {
printf(" %d"+!i,a[pos[i]]);
}
return 0;
}
解法2
次の順序でツリーを巡回し、次の順序で出力を巡回します.
#include
#define N 102
using namespace std;
int n;
int a[N],b[N];
int pos;
void build(int id) {
if(id > n) return ;
build(id<<1);
build(id<<1|1);
b[id] = a[++pos];
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
cin >> a[i];
}
build(1);
for(int i=1; i<n; i++) {
cout << b[i] << " ";
}
cout << b[n];
return 0;
}