AcWing 1589. 构建二叉搜索树
原题链接
中等
作者:
lu1zero9
,
2022-02-24 09:00:02
,
所有人可见
,
阅读 172
思路:首先将各个结点的左右子节点存储好;然后输入各个结点的值 对值进行排序后 模拟中序遍历dfs 将各个结点对应的值填入w中存储好;然后通过bfs 模拟层序遍历将各个点按层序遍历的顺序存入ans当中;最后输出各个点对应的权值即可。
#include<bits/stdc++.h>
using namespace std;
const int N=110;
unordered_map<int,int> l,r;
int w[N];//结点的值
int a[N];
int idx=0;
int n;
vector<int> ans;
void dfs(int root){
//if(root>n)return;
if(l[root]!=-1)dfs(l[root]);
w[root]=a[idx++];
if(r[root]!=-1)dfs(r[root]);
}
void bfs(){
queue<int> q;
q.push(0);
while(!q.empty()){
int t=q.front();
q.pop();
if(l[t]!=-1){
q.push(l[t]);
}
if(r[t]!=-1){
q.push(r[t]);
}
ans.push_back(t);
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
string a,b;
cin>>a>>b;
l[i]=stoi(a);
r[i]=stoi(b);
}
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
dfs(0);
bfs();
cout<<w[ans[0]];
for(int i=1;i<n;i++)cout<<" "<<w[ans[i]];
return 0;
}