TopCoder

User's AC Ratio

94.3% (133/141)

Submission's AC Ratio

58.4% (205/351)

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 1

6
-10
10
100
1000
10000
1000000

Sample Output 1

-10 10 100 1000 10000 1000000

Hints

Problem Source

原TIOJ1609 / Problem Setter: suhorng

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

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