题意:
给出一个完全二叉搜索树的键值序列,要求输出层序输出
要点:
完全二叉搜索树的根节点是可以唯一确定的,所以一开始排序一下,再用dfs即可。这题我思路是想到了,但是生成根节点的地方写的有点问题,然后要输出层序是可以用dfs中序遍历再加一个数组直接输出的,这里可以学习一下。
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<string.h>
#include<sstream>
#include<functional>
#include<algorithm>
#define lowbit(i) ((i)&(-i))
using namespace std;
const int INF = 0xfffff;
const int maxn = 2055;
int num[maxn],res[maxn];
int n;void dfs(int l, int r,int pos) {if (l > r)return;int n = r - l + 1;int exp = log(n+1) / log(2);int last = n - (pow(2, exp) - 1);int root = l + (pow(2, exp - 1)-1) + min(last, (int)pow(2, exp - 1));//cout << exp<<" "<<last<<root << endl;res[pos] = root;dfs(l, root-1,2*pos+1);dfs(root+1, r,2*pos+2);
}int main() {scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &num[i]);}sort(num, num + n);dfs(0, n - 1,0);for (int i = 0; i < n-1; i++)printf("%d ", num[res[i]]);printf("%d\n", num[res[n - 1]]);return 0;
}