7 Levels of Binary Search Tree

Time Limit: 1 Second
Memory Limit: 32768 KB

Given *N* numbers and the structure of a binary search tree. Please output the postorder traversal sequence of the tree.

For example, given numbers 1~7 and the tree structure in the figure 1, we can fill in the numbers as shown in the figure 2. Hence the postorder traversal sequence is {2, 4, 3, 1, 7, 6, 5}.

**
Note
**

It is garanteed that the level of a tree is never more than 7 (the root is at level 1).

**
Input
**

Each case starts with a line containing an integer *N* (*N* <= 127) followed by *N* non-negative integers which are supposed to be in the tree.

The next line gives the number of levels, *L*, of the binary search tree.

In the following *L*-1 lines, each line contains the numbers of nodes in the left- and right-subtrees of an upper-level node (the root level is omitted). If the upper-level node has no child, nothing will be shown in the next line.

The figure 1 is described by Sample Input. The 1st line of the tree contains 4 and 2, meaning that the root has 4 nodes in its left-subtree and 2 nodes in its right-subtree. The 2nd line contains 0, 3, 0, and 1, meaning that for the root of the left-subtree, there are 3 nodes in its right-subtree; for the root of the right-subtree, there are 1 node in its right-subtree. Since at level 3, there is only one subtree which contains more than 1 node, the 3rd line indicates that the root of this subtree has 1 left child and 1 right child.

**
Output
**

For each test case, output the required postorder traversal sequence in a line. The numbers must be seperated by one space, and there must be no extra space at the end of the sequence.

**
Sample Input
**

7 3 2 1 5 4 6 7
4
4 2
0 3 0 1
1 1

**
Sample Output
**

2 4 3 1 7 6 5

Author:

**CHEN, Yue**
Source:

**ZOJ 7th Anniversary Contest**
Submit
Status