PAT (Advanced Level) Practice 1099 Build A Binary Search Tree (30 分) 凌宸1642
题目描述：
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.
译：定义一颗拥有如下性质的二叉树为一颗二叉搜索树(BST):
- 左子树只包含比当前结点的值小的结点。
- 右子树只包含比当前结点的值大的结点。
- 左右子树必须也是一颗二叉搜索树。
给定一颗二叉树的结构和一不含重复数字的值序列，将该树填充为一颗二叉搜索树的方法是唯一的。你应该输出二叉搜索树的层序遍历序列。样例图如下图1和图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…
译：每个输入文件包含一个测试，第一行给定一个正整数 N (≤100) 表示二叉树的总结点数目。接下来N行，每行用 left_index right_index给出这个结点的左右孩子结点的索引值，结点的编号从 0 到 N -1 ，并且固定根节点为0号结点。如果这个结点的孩子节点不存在，用一个 -1表示。最后一行是N个不同的正整数。
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 42
Sample Output (样例输出):
58 25 82 11 38 67 45 73 42
The Idea：
首先是建树，然后对正整数序列进行升序排序，利用中序遍历对每个结点的值进行填充即可得到二叉搜索树，最后对其进行层序遍历即可。
- 建树，由于N的范围很小，可以直接使用结构体来表示节点。
- 找到根节点，题目中说明0号结点为根节点，故不需要求。
- 二叉树的中序遍历，利用全局的 index 值，进行中序遍历填充(因为二叉搜索树的中序遍历序列是升序的)。
- 对填充完值得二叉搜索树进行层序遍历，得到层序序列并按要求输出即可。
The Codes:
#include<bits/stdc++.h>
using namespace std ;
struct NODE{
int fa , left , right , val ;
}Node[110] ;
int n , l , r , num[110] , ind = 0 ;
vector<int> level ;
void inOrder(int root){
if(root == -1) return ;
inOrder(Node[root].left ) ;
Node[root].val = num[ind ++] ;
inOrder(Node[root].right) ;
}
void levelOrder(int root){
queue<int> q ;
q.push(root) ;
while(!q.empty()){
int top = q.front() ;
q.pop() ;
level.push_back(Node[top].val) ;
if(Node[top].left != -1) q.push(Node[top].left) ;
if(Node[top].right != -1) q.push(Node[top].right) ;
}
}
int main(){
cin >> n ;
for(int i = 0 ; i < n ; i ++){
cin >> l >> r ;
Node[i].left = l ;
Node[i].right = r ;
if(l != -1) Node[l].fa = i ;
if(r != -1) Node[r].fa = i ;
}
for(int i = 0 ; i < n ; i ++) cin >> num[i] ;
sort(num , num + n) ;
inOrder(0) ;
levelOrder(0) ;
for(int i = 0 ; i < n ; i ++)
printf("%d%c" , level[i] , ((i == n-1)?'\n':' ')) ;
return 0 ;
}