重建二元搜尋樹(Rebuild BST from Level Order)
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
題目:重建二元搜尋樹(Rebuild BST from Level Order)
題目描述:
給你一列整數,代表一棵二元搜尋樹(Binary Search Tree, BST)的層序遍歷(Level Order Traversal)結果。
請你根據這個層序遍歷結果,重建唯一的一棵合法 BST,並輸出這棵 BST 的 後序遍歷(Post-order Traversal)結果。
在 BST 中,對於每個節點 x
,其左子樹中所有節點的值均小於 x.val
,右子樹中所有節點的值均大於 x.val
。輸入不包含重複的數字。
🔢 輸入格式:
- 第一行一個整數
n
(1 ≤ n ≤ 1000),表示節點數。 - 第二行
n
個整數,為 BST 的層序遍歷結果。數字之間以空格分隔,保證所有數字互不相同,且構成一棵合法 BST 的層序遍歷。
🖥️ 輸出格式:
- 輸出一行,為重建後 BST 的**後序遍歷(Post-order)**結果,數字之間以空格分隔。
🧪 範例輸入 1:
7
5 3 8 1 4 6 9
✅ 範例輸出 1:
1 4 3 6 9 8 5
🧠 範例說明:
輸入的 BST 結構為:
5
/ \
3 8
/ \ / \
1 4 6 9
其後序遍歷為:1 4 3 6 9 8 5
📌 限制條件:
- 所有節點值互不相同。
- 不保證層序輸入為滿樹,也不保證每層節點數完整。
- 構建方式為:從空樹開始,依序將層序中的每個節點「以 BST 插入法」插入。
20250509_C++_練習題
- Status
- Done
- Problem
- 4
- Open Since
- 2025-5-8 0:00
- Deadline
- 2025-5-17 23:59
- Extension
- 24 hour(s)