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 (输入说明):

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