TopCoder

User's AC Ratio

95.2% (20/21)

Submission's AC Ratio

70.2% (33/47)

Tags

Description

二元搜尋樹(Binary Search Tree),也稱有序二元樹(ordered binary tree)、排序二元樹(sorted binary tree),是指一棵空樹或者具有下列性質的二元樹:
1. 若任意節點的左子樹不空,則左子樹上所有節點的值均小於它的根節點的值。
2. 任意節點的右子樹不空,則右子樹上所有節點的值均大於它的根節點的值。
3. 任意節點的左、右子樹也分別為二元搜尋樹。
4. 沒有鍵值相等的節點(no duplicate nodes)。(from wikipedia)

一個二元搜尋樹中序遍歷的結果即為所有鍵值排序後的結果。

圖一:一個二元搜尋樹的例子(範例)。

現在給你一個二元搜尋樹前序遍歷的結果,請你輸出此二元搜尋樹後序遍歷的結果。

Input Format

輸入的第一行包含一個正整數 $N\,(N \leq 2000)$,代表節點的個數。
接下來的 $N$ 行為一個二元搜尋樹前序遍歷的結果,每行包含一個整數 $k_i$ $(0 \leq k_i \leq 10 ^ 5 -1)$ ,為該節點的值。
保證 $k_i \neq k_j \,(i \neq j)$。

Output Format

請輸出測試資料內二元搜尋樹後序遍歷的結果,每個數字一行。

Sample Input 1

9
50
30
24
5
28
45
98
52
60

Sample Output 1

5
28
24
45
30
60
52
98
50

Hints

Problem Source

NEOJ Problem 48

Subtasks

No. Testdata Range Constraints Score
1 0~2 $N \leq 10$。 30
2 3~9 無額外限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 2
4 1000 65536 65536 2
5 1000 65536 65536 2
6 1000 65536 65536 2
7 1000 65536 65536 2
8 1000 65536 65536 2
9 1000 65536 65536 2