AcWing 1550. 完全二叉搜索树
原题链接
中等
作者:
goldstine
,
2021-07-18 13:30:43
,
所有人可见
,
阅读 308
题目描述
已知中序序列,构建完全二叉树 输出层次序列
通过中序序列递归构建完全二叉树levelorder[u]=a[k++];
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int a[N];
int n;
int k=0;
int levelorder[N];
void dfs(int u){//采用中序序列进行建树
if(u>n){
return ;
}
dfs(2*u);
levelorder[u]=a[k++];
dfs(2*u+1);
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
//二叉搜索树的中序遍历是递增序列
sort(a,a+n);
dfs(1);
for(int i=1;i<=n;i++){
cout<<levelorder[i]<<" ";
}
cout<<endl;
return 0;
}