#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 插入法」插入。