🧠 所需知識點

1. 二元搜尋樹（BST）的定義：

   • 每個節點的左子樹中的節點值都小於該節點值。
   • 每個節點的右子樹中的節點值都大於該節點值。
   • 中序遍歷 BST 時，會得到一個嚴格遞增的數列。

2. 層序遍歷（Level Order Traversal）：

   • 是按照一層一層，由上而下、由左到右的順序訪問節點。
   • 通常透過**佇列（Queue）**來實作。

3. 樹的建構：

   • 對於給定的層序輸入（可能包含 "null" 表示空節點），需要正確連接左右子節點。

4. 中序遍歷（Inorder Traversal）：

   • 遞迴訪問左子樹 → 節點本身 → 右子樹。

---

🔍 題目目標

• 給定包含 "null" 的層序輸入序列。
• 還原出 BST（雖然格式上是層序輸入，但其實是已構建好的一棵 BST，只是用層序形式表達）。
• 輸出這棵樹的中序遍歷結果。

---

✅ 程式碼逐行解析

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

定義樹的節點結構，每個節點有整數值、左子和右子。

---

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

標準的中序遍歷函數，遞迴訪問左→根→右，把結果存入 result 向量中。

---

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

讀入節點數（包含 "null"），代表整個層序輸入陣列長度。

---

    vector<string> v = {};
    for(int i = 0; i < n; i++){
        string x;
        cin >> x;
        v.push_back(x);
    }

讀入 n 個字串，存入 v，每個字串是數字或 "null"。

---

    queue<Node*> q = {};

    if(v[0] == "null"){
        return 0;
    }

    Node* root = new Node(stoi(v[0]));
    q.push(root);

用 queue 來模擬層序建樹。 若第一個節點是 null，整棵樹不存在，提早結束。 否則以 v[0] 建立根節點。

---

    int i = 1;
    while(!q.empty() && i < v.size()){
        Node* node = q.front();
        q.pop();

從 queue 中取出當前節點，嘗試為它建左右子節點。

---

        if(i < v.size() && v[i] != "null"){
            node->left = new Node(stoi(v[i]));
            q.push(node->left);
        }
        i++;

建立左子節點，如果不是 "null" 的話。

---

        if(i < v.size() && v[i] != "null"){
            node->right = new Node(stoi(v[i]));
            q.push(node->right);
        }
        i++;
    }

同理，建立右子節點。

---

    vector<int> result = {};
    inorder(root, result);

呼叫前面定義的 inorder 函數，將中序結果放入 result 向量中。

---

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

輸出最終中序遍歷結果，注意空格格式。

---

🖼️ 示意圖說明

以輸入 5 3 8 1 4 6 9 null null 為例，其結構為：

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

中序遍歷順序為：

左子樹（1 3 4）→ 根（5）→ 右子樹（6 8 9）
→ 輸出：1 3 4 5 6 8 9

---

🧪 時間與空間複雜度

• 時間複雜度：O(n)，每個節點最多處理一次。
• 空間複雜度：O(n)，佇列與儲存結果用的向量均為線性空間。

---

✅ 小結

這題的重點不在於建構 BST（因為題目保證輸入的是合法 BST 的層序遍歷），而是：

• 正確還原層序樹結構（有 "null" 的情況）。
• 使用中序遍歷列印結果。

若你熟悉樹的基本結構與遍歷方法，這題能幫助你熟練 構建樹 + 遍歷輸出 的基礎功。