使用的map

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
const int N=110;
//左节点，右节点，权值，中根，层次遍历
int l[N],r[N],val[N],in[N],q[N];
int idx,n;//idx为中根的索引
map<int,int> mp;
//中根遍历一下，把中根的每个编号存到in数组中
void inorder(int root){
    if(l[root]!=-1) inorder(l[root]);
    in[idx++]=root;
    if(r[root]!=-1) inorder(r[root]);
}
//level层次遍历后，结果会留着q数组
void level(int root){
    int hh=0,tt=-1;
    q[++tt]=root;
    while(hh<=tt){
        int t=q[hh++];
        if(l[t]!=-1) q[++tt]=l[t];
        if(r[t]!=-1) q[++tt]=r[t];
    }
}
int main(){
    scanf("%d",&n);
    //输入节点数据
    for(int i=0;i<n;i++){
        scanf("%d%d",&l[i],&r[i]);
    }
    //输入节点的权值
    for(int i=0;i<n;i++){
        scanf("%d",&val[i]);
    }
    sort(val,val+n);//排序后就是中序遍历对应的权值
    inorder(0);//进行中根遍历，把中根对应的节点编号存的in数组
    for(int i=0;i<n;i++) mp[in[i]]=val[i];//让中根时节点的编号和权值产生映射
    level(0);//层次遍历一下，层次编号保存到q数组
    //按层次遍历的节点编号顺序输出一遍对应权值
    for(int i=0;i<n;i++){
        if(i!=0) printf(" ");
        printf("%d",mp[q[i]]);
    }
    return 0;
}

小修改，使用模拟hash

主要原因是noi比赛没有unordered_map这个库，故模拟实现

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=110,H=997,null=0x3f3f3f3f;//H和null哈希专用
//左节点，右节点，权值，中根，层次遍历
int l[N],r[N],val[N],in[N],q[N];
int idx,n;//idx为中根的索引
int h[H],mp[H];//h和mp哈希专用
int find(int x){//找可以的下标
    int t=(x%H+H)%H;
    while(h[t]!=null&&h[t]!=x){
        t++;
        if(t==H) t=0;
    }
    return t;
}
//中根遍历一下，把中根的每个编号存到in数组中
void inorder(int root){
    if(l[root]!=-1) inorder(l[root]);
    in[idx++]=root;
    if(r[root]!=-1) inorder(r[root]);
}
//level层次遍历后，结果会留着q数组
void level(int root){
    int hh=0,tt=-1;
    q[++tt]=root;
    while(hh<=tt){
        int t=q[hh++];
        if(l[t]!=-1) q[++tt]=l[t];
        if(r[t]!=-1) q[++tt]=r[t];
    }
}
int main(){
    memset(h,0x3f,sizeof h);//重要的hash初始化，多次忘写
    scanf("%d",&n);
    //输入节点数据
    for(int i=0;i<n;i++){
        scanf("%d%d",&l[i],&r[i]);
    }
    //输入节点的权值
    for(int i=0;i<n;i++){
        scanf("%d",&val[i]);
    }
    sort(val,val+n);//排序后就是中序遍历对应的权值
    inorder(0);//进行中根遍历，把中根对应的节点编号存的in数组
    for(int i=0;i<n;i++){//让中根时节点的编号和权值产生映射
        int hi=find(in[i]); //使用了中根的编号做了映射，没有用权值，因为权值的范围可能很大，hash可能有重复，导致速度变慢，但总体来说没有多大影响，还有数量的限制。
        h[hi]=in[i],mp[hi]=val[i];
    }
    level(0);//层次遍历一下，层次编号保存到q数组
    //按层次遍历的节点编号顺序输出一遍对应权值
    for(int i=0;i<n;i++){
        if(i!=0) printf(" ");
        printf("%d",mp[find(q[i])]);
    }
    return 0;
}