二叉搜索树 (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最近每天都会写2-3道题保持手感，遇到好的题就会上传~
分析：之前从来没有系统的写过树的题，感觉像这种二叉搜索树的题应该是有板子的，我是按照自己对这道题的理解，用函数dfs1，求出每一个节点的左子树有几个节点，这个是用来确定该节点应该填哪个数用的 ，因为假设根节点的左子树有5个节点，那我们就可以知道根节点是第6大的数，我们就可以把c[6]赋值给根节点，因此我们还要把输入的c[]数组排一下序，填每个节点的值时，我用了dfs函数，深度遍历填写的，这里需要注意的时，一个节点的左子树有k个节点不代表该节点就填c[k](从0到n-1的下标），这只能说明该节点在以该节点为根节点的树中排第k+1，因此dfs函数还要添加参数ll，rr作为左右范围。最后用一个bfs遍历输出答案，因为要求的是层序遍历结果。
代码如下：
#include <bits/stdc++.h>using namespace std;
struct node{
int l,r,id;
int w;
}adj[110];
int n,a,b;
int c[101],st[101],al[101];
int dfs1(int id)
{int ll=0,rr=0;if(adj[id].l) ll = dfs1(adj[id].l);if(adj[id].r) rr = dfs1(adj[id].r);al[id]=ll;return ll+rr+1;
}
void dfs(int id,int ll,int rr)
{//cout<<id<<" ";int num=al[id];adj[id].w=c[num+ll];if(adj[id].l) dfs(adj[id].l,ll,num+ll-1);if(adj[id].r) dfs(adj[id].r,num+ll+1,rr);
}
void bfs()
{queue<int>q;q.push(0);while(q.size()){int u=q.front();q.pop();cout<<adj[u].w<<" ";if(adj[u].l)q.push(adj[u].l);if(adj[u].r)q.push(adj[u].r);}
}
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>a>>b;if(a!=-1) adj[i].l=a;if(b!=-1) adj[i].r=b;}for(int i=0;i<n;i++) cin>>c[i];dfs1(0);sort(c,c+n);dfs(0,0,n-1);bfs();return 0;
}
