构建二叉搜索树

• 这里先是把每个id对应的数字填进w[i]（利用BST的中序遍历是有序的这个特点递归填入），然后通过层序遍历通过id得到相应id的结点里面填的数字。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int N = 110;

int n;
int l[N], r[N];
int a[N];
int w[N]; // w[i]表示id为i的结点里面存的值是w[i]
int k; // 用来记录现在用到了a的第几个数

void dfs(int u)
{
    if (u == -1) return;

    dfs(l[u]);
    w[u] = a[k ++ ]; // id为i的结点里面存的值是w[i]，比如图中id为1的结点存的是25，为6的结点存的是82
    dfs(r[u]);
}

void bfs()
{
    vector<int> v;
    queue<int> q;
    q.push(0);

    while (q.size())
    {
        int t = q.front();
        q.pop();
        v.push_back(w[t]);
        if (l[t] != -1) q.push(l[t]);
        if (r[t] != -1) q.push(r[t]);
    }

    printf("%d", v[0]);
    for (int i = 1; i < v.size(); i ++ ) printf(" %d", v[i]);
}

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);

    dfs(0);
    bfs();

    return 0;
}