🧠 題目考察的知識點：

1. 二元搜尋樹（BST）的性質：

   • 對於每個節點 x，其左子樹中所有節點的值都小於 x.val，右子樹中所有節點的值都大於 x.val。

2. BST 的構建方法：

   • 根據層序遍歷結果，依序將每個節點「使用 BST 插入邏輯」插入到樹中。

3. 二叉樹的後序遍歷（Post-order Traversal）：

   • 遍歷順序為：左子樹 ➜ 右子樹 ➜ 根節點。

🔍 程式碼逐行解析

#include <iostream>
#include <vector>
using namespace std;

引入標準輸入輸出與容器 vector，用來處理輸入數據與儲存遍歷結果。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(NULL), right(NULL) {}
};

定義二元樹節點結構 TreeNode，包含值 val、左右子樹指標 left 和 right。

TreeNode* insert(TreeNode* root, int val) {
    if (root == NULL) return new TreeNode(val);
    if (val < root->val)
        root->left = insert(root->left, val);
    else
        root->right = insert(root->right, val);
    return root;
}

這是 BST 的插入函式。若根節點為 NULL，則新建節點；否則依照 BST 性質往左或右遞迴插入。

void postOrder(TreeNode* root, vector<int>& result) {
    if (root == NULL) return;
    postOrder(root->left, result);
    postOrder(root->right, result);
    result.push_back(root->val);
}

進行後序遍歷，將節點值依「左 ➜ 右 ➜ 根」順序加入 result 容器中。

int main() {
    int n;
    cin >> n;

讀入節點數 n。

    vector<int> levelOrder(n);
    for (int i = 0; i < n; ++i) {
        cin >> levelOrder[i];
    }

讀入層序遍歷的節點值，存入 levelOrder 陣列。

    TreeNode* root = NULL;
    for (int val : levelOrder) {
        root = insert(root, val);
    }

從空樹開始，依序將每個值插入，重建整棵 BST。

    vector<int> result;
    postOrder(root, result);

呼叫後序遍歷函式，將結果存入 result。

    for (int i = 0; i < result.size(); ++i) {
        if (i > 0) cout << " ";
        cout << result[i];
    }
    cout << endl;

按照格式輸出後序遍歷結果（中間空格分隔）。

    return 0;
}

程式結束。

🌳 示意圖（以範例為例）

輸入層序： 5 3 8 1 4 6 9

構建過程如下：

Step 1: 插入 5 為根  
Step 2: 插入 3 ➜ 進左邊 ➜ 成為 5 的左子  
Step 3: 插入 8 ➜ 進右邊 ➜ 成為 5 的右子  
Step 4: 插入 1 ➜ 左左  
Step 5: 插入 4 ➜ 左右  
Step 6: 插入 6 ➜ 右左  
Step 7: 插入 9 ➜ 右右

最終 BST 結構：

        5
      /   \
     3     8
    / \   / \
   1  4  6  9

其後序遍歷為：1 4 3 6 9 8 5

✅ 小結

本題考察：

• BST 插入邏輯
• 二叉樹後序遍歷
• 樹的重建與遍歷輸出能力

難度屬於中等偏下，是經典的資料結構練習題目，適合用來鞏固 BST 操作概念。