自用资料
二叉搜索树的中序遍历结果是递增的永远是解题的突破口
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int l[N], r[N];
int w[N], w2[N];
int n, idx;
void dfs(int u)
{
if(u == -1) return;
dfs(l[u]);
w2[u] = w[idx++];
dfs(r[u]);
}
void bfs()
{
queue<int> q;
q.push(0);
while(q.size())
{
int t = q.front();
q.pop();
cout << w2[t] << " ";
if(l[t] != -1) q.push(l[t]);
if(r[t] != -1) q.push(r[t]);
}
}
int main()
{
cin >> n;
for(int i = 0;i < n;i ++)
{
int a, b;
cin >> a >> b;
l[i] = a;
r[i] = b;
}
for(int i = 0;i < n;i ++) cin >> w[i];
sort(w, w + n);
dfs(0);
bfs();
}