分析
- 将输入的数据从小到大排序,然后中序遍历将数据依次赋值给每个节点即可;最后BFS遍历数据结果。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int w[N], l[N], r[N]; // 每个节点的数值、左孩子编号、右孩子编号
int a[N];
int q[N];
void dfs(int u, int &k) {
if (u == -1) return;
dfs(l[u], k);
w[u] = a[k++];
dfs(r[u], k);
}
void bfs() {
int hh = 0, tt = -1;
q[++tt] = 0;
while (hh <= tt) {
int t = q[hh++];
printf("%d ", w[t]);
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", &a[i]);
sort(a, a + n);
int k = 0;
dfs(0, k);
bfs();
return 0;
}