TopCoder

Thumb tumblr nlxw0sxc2d1unbsixo1 540
Trash
><

User's AC Ratio

97.1% (66/68)

Submission's AC Ratio

60.0% (87/145)

Tags

Description


二元搜尋樹是最基礎的一種動態資料結構,支持動態的新增、刪除、查找元素等操作,

我們也可以視二元搜尋樹為一個可動態維護的集合。

此外,二元搜尋樹的效率大致取決於樹的高度,而樹的高度則由元素插入的順序決定。

最壞情況下,對二元搜尋樹做n次插入操作可能需要O(n2) 的時間。

假設現在我們已經知道所有元素插入一棵二元搜尋樹的順序,

請問所有元素皆插入後,二元搜尋樹的中序遍歷結果為 ?

Input Format

第一行有一個正整數n,代表我們總共插入了n個不同的元素(1≦n≦1,000,000)。
接下來的n行,每一行有一個整數,第i+1行代表第i個插入的元素vi
(-230≦vi≦230)。

Output Format

請輸出一行,總共有n個整數,代表二元搜尋樹的中序遍歷結果。整數間請以一個空白
隔開。

Sample Input

6
-10
10
100
1000
10000
1000000

Sample Output

-10 10 100 1000 10000 1000000

Hints

Problem Source

原TIOJ1609 / Problem Setter: suhorng

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144
5 10000 65536 262144
6 10000 65536 262144
7 10000 65536 262144
8 10000 65536 262144
9 10000 65536 262144