PAT A1099

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 42
Sample Output:
58 25 82 11 38 67 45 73 42

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include "stdio.h"
#include "math.h"
#include "string.h"
//#include "iostream"
//#include "stdlib.h"
#include "vector"
//#include "set"
//#include "map"
//#include "stack"
#include "queue"
#include "algorithm"
using namespace std;

//typedef long long LL;
const int maxn = 110;
int n;
struct node{
int data;
int left, right;
}Node[maxn];
int number[maxn], num = 0;
void inOrder(int root){
if (root == -1) {
return;
}
inOrder(Node[root].left);
Node[root].data = number[num++];
inOrder(Node[root].right);
}
void levelOrder(int root){
queue<int> q;
q.push(root);
num = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
num++;
printf("%d", Node[now].data);
if (num < n) {
printf(" ");
}
if (Node[now].left != -1) {
q.push(Node[now].left);
}
if (Node[now].right != -1) {
q.push(Node[now].right);
}
}
}
int main(){
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &Node[i].left, &Node[i].right);
}
for (int i = 0; i < n; i++) {
scanf("%d", &number[i]);
}
sort(number, number + n);//从小到大排序
inOrder(0);
levelOrder(0);
return 0;
}