47 . 二元搜尋樹
TopCoder
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
50
30
24
5
28
45
98
52
60
Sample Output 1
5
28
24
45
30
60
52
98
50
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 |