二叉搜索树 (BST) 递归定义为具有以下属性的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
- 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
- 它的左、右子树也分别为二叉搜索树
给定二叉树的具体结构以及一系列不同的整数，只有一种方法可以将这些数填充到树中，以使结果树满足 BST 的定义。
请你输出结果树的层序遍历。
示例如图 1 和图 2 所示。
输入格式
第一行包含一个正整数 N，表示树的结点个数。
所有结点的编号为 0∼N−1，并且编号为 0 的结点是根结点。
接下来 N 行，第 i 行（从 0 计数）包含结点 i 的左右子结点编号。如果该结点的某个子结点不存在，则用 −1 表示。
最后一行，包含 N 个不同的整数，表示要插入树中的数值。
输出格式
输出结果树的层序遍历序列。
数据范围
1≤N≤100
输入样例：
9
1 6
2 3
-1 -1
-1 4
5 -1
-1 -1
7 -1
-1 8
-1 -1
73 45 11 58 82 25 67 38 42输出样例：
58 25 82 11 38 67 45 73 42代码实现：
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=105;
int l[N],r[N],res[N],a[N],cnt,idx;
void dfs(int idx){
if(l[idx]!=-1)dfs(l[idx]);
res[idx]=a[cnt++];
if(r[idx]!=-1)dfs(r[idx]);
}
void bfs(int x){
queue<int>q;
q.push(x);
while(q.size()){
int t=q.front();
q.pop();
if(!idx)cout<<res[t];
else cout<<" "<<res[t];
idx++;
if(l[t]!=-1)q.push(l[t]);
if(r[t]!=-1)q.push(r[t]);
}
}
int main(){
int n;
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(0);
return 0;
}