#LAISIR11. 重建二元搜尋樹(Rebuild BST from Level Order)
重建二元搜尋樹(Rebuild BST from Level Order)
題目:重建二元搜尋樹(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 插入法」插入。
Related
In following homework: