1099. Build A Binary Search Tree (30)

時間の制限
100 ms
メモリ制限
65536 kB
コード長制限
16000 B
クイズルーチン
Standard
作成者
CHEN, Yue
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
この問題の情報量はとても大きくて静的な配列で木を建てて最後に階層で遍歴します
#include #include using namespace std; struct node {     int val, l, r; }g[110]; int a[110]; queueq; int n, k; void mid(int k1); void travel(); int main() {     scanf("%d", &n);     for(int i=0;i     {         int x, y;         scanf("%d %d", &x, &y);         g[i].l=x;         g[i].r=y;     }     for(int i=0;i     {         scanf("%d", &a[i]);     }     sort(a,a+n);     k=0;     mid(0);     travel();     printf("");     return 0; } void mid(int k1) {     if(g[k1].l!=-1)     {         mid(g[k1].l);     }     g[k1].val=a[k];     k++;     if(g[k1].r!=-1)     {         mid(g[k1].r);     }     return ; } void travel() {     if(g[0].val==-1)     {         return ;     }     else     {         struct node e=g[0];         q.push(e);         int flag=0;         while(!q.empty())         {             e=q.front();             q.pop();             if(flag==0)             {                 printf("%d",e.val);                 flag=1;             }             else             {                 printf("%d",e.val);             }             if(e.l!=-1)             {                 q.push(g[e.l]);             }             if(e.r!=-1)             {                 q.push(g[e.r]);             }         }     }     return ; }