1099. Build A Binary Search Tree (30)
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
- Both the left and right subtrees must also be binary search trees.
Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format "left_index right_index", provided that the nodes are numbered from 0 to N-1, and 0 is always the root. If one child is missing, then -1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.
Output Specification:
For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.
Sample Input:
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 42Sample Output:
58 25 82 11 38 67 45 73 42
题意：给定n个数插入BST，并且插入数值后的BST结构已经确定，依据这个结构来推断BST上每个节点对应的数值，并且层序遍历BST。
思路：一开始的思路比较复杂，将n各数值从小到大排列，我先搜索出了BST上每个节点左右子树的节点个数。在此基础上就可以递推的确定每个节点对应的数值在数列上的位置。假设
已经确定某一个节点x对应的数值在数列上的位置pos,那么其节点x的左儿子的数值所在位置与pos的距离间隔就是左儿子的右子树节点个数（原因：比左儿子的数值大又比x的数值小，这些节点的数值当然都存储在左儿子的右子树上），从而可以推断左儿子的数值。右儿子的数值推断方法类似。
但其实不需要如此复杂，按照中序遍历的顺序就可以直接推断出各个节点上对应的数值。。。
AC代码：
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<set>
#include<queue>
using namespace std;
#define INF 0x3f3f3f
#define N_MAX 100+5
int n;
struct Node {
int l_child, r_child;
int key;
}node[N_MAX];
vector<int>vec;
pair<int, int>num[N_MAX];
/*
int dfs(int x) {//查询每个节点左右儿子的数量
int left_num=0, right_num=0;
if(node[x].l_child!=-1)left_num = dfs(node[x].l_child);
if (node[x].r_child != -1)right_num = dfs(node[x].r_child);
num[x] = make_pair(left_num, right_num);
return right_num + left_num+1;
} void dfs2(int x,int pos) {//节点x上的数值为vec[pos]，考虑节点x与儿子节点的距离来推断儿子节点的位置
node[x].key = vec[pos];
int pos_left = pos - num[node[x].l_child].second - 1;
int pos_right = pos + num[node[x].r_child].first + 1;
if(node[x].l_child!=-1)dfs2(node[x].l_child, pos_left);
if(node[x].r_child!=-1)dfs2(node[x].r_child, pos_right);
}*/ int step = ;
void inorder(int x) {//其实按照中序遍历的顺序就可以依次确定每个节点的数值key
if(node[x].l_child!=-)inorder(node[x].l_child);
node[x].key = vec[step++];
if(node[x].r_child!=-)inorder(node[x].r_child);
} int output[N_MAX];
void bfs(int root) {
queue<int>que;
que.push(root);
int cnt = ;
while(!que.empty()) {
int x = que.front(); que.pop();
output[cnt++] = node[x].key;
if(node[x].l_child!=-)que.push(node[x].l_child);
if(node[x].r_child!=-)que.push(node[x].r_child);
}
} int main(){
while (scanf("%d",&n)!=EOF) {
for (int i = ; i < n;i++) {
int l, r; scanf("%d%d",&l,&r);
node[i].l_child = l, node[i].r_child = r;
}
vec.resize(n);
for (int i = ; i < n; i++)scanf("%d",&vec[i]);
sort(vec.begin(),vec.end());
//dfs(0);
//dfs2(0, num[0].first);
inorder();
bfs();
for (int i = ; i < n; i++)printf("%d%c",output[i],i+==n?'\n':' ');
}
return ;
}