二叉搜索树的性质：按照中序遍历是递增的

这道题既考察了树的深搜，也考察了宽搜，是道好题！

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int w[N], l[N], r[N];
int a[N], 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 = 0;
    q[0] = 0;
    while(hh <= tt)
    {
        int t = q[hh ++];
        cout << w[t] << ' ';
        if(l[t] != -1) q[++ tt] = l[t];
        if(r[t] != -1) q[++ tt] = r[t];
    }
}


int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++ ) cin >> l[i] >> r[i];
    for(int i = 0;i < n;i ++ ) cin >> a[i];
    sort(a,a + n);

    int k = 0;
    dfs(0,k);
    bfs();

    return 0;
}