二元搜尋樹(Binary Search Tree),也稱有序二元樹(ordered binary tree)、排序二元樹(sorted binary tree),是指一棵空樹或者具有下列性質的二元樹:
1. 若任意節點的左子樹不空,則左子樹上所有節點的值均小於它的根節點的值。
2. 任意節點的右子樹不空,則右子樹上所有節點的值均大於它的根節點的值。
3. 任意節點的左、右子樹也分別為二元搜尋樹。
4. 沒有鍵值相等的節點(no duplicate nodes)。(from wikipedia)
一個二元搜尋樹中序遍歷的結果即為所有鍵值排序後的結果。
圖一:一個二元搜尋樹的例子(範例)。
現在給你一個二元搜尋樹前序遍歷的結果,請你輸出此二元搜尋樹後序遍歷的結果。
輸入的第一行包含一個正整數 $N\,(N \leq 2000)$,代表節點的個數。
接下來的 $N$ 行為一個二元搜尋樹前序遍歷的結果,每行包含一個整數 $k_i$ $(0 \leq k_i \leq 10 ^ 5 -1)$ ,為該節點的值。
保證 $k_i \neq k_j \,(i \neq j)$。
請輸出測試資料內二元搜尋樹後序遍歷的結果,每個數字一行。
NEOJ Problem 48
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~2 | $N \leq 10$。 | 30 |
2 | 3~9 | 無額外限制 | 70 |