以下是這道題目的詳細 題解說明，包括知識點分析、程式碼逐行解析與示意圖解釋：

---

🧠 所需知識點

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

• 對於任一節點：

  • 左子樹的所有值 < 該節點值。
  • 右子樹的所有值 > 該節點值。

• 中序遍歷結果為 嚴格遞增序列。

2. 完全先序遍歷（Complete Preorder Traversal）：

• 格式：根 → 左 → 右。
• 特別之處：即使是空節點也會記錄成 "null"，使整棵樹的結構完整保留。
• 因此，可以直接根據輸入順序重建出原來的 BST 結構。

3. 樹的重建：

• 使用遞迴依序從先序列表建構出原樹：

  • 遇到 "null" 表示空節點，返回 NULL。
  • 否則創建新節點，繼續建構左子與右子。

---

🧩 題目理解重點

你獲得的是一棵 BST 的完全先序遍歷，所以可依據此序列還原出整棵樹。

之後進行中序遍歷，即可獲得升序的節點值序列。

---

🔍 程式碼逐行解析

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

定義樹節點結構，包含整數值與左右子節點指標。

---

Node* buildTrees(vector<string>& preorder, int& i){
    if(i >= preorder.size() || preorder[i] == "null"){
        i += 1;
        return NULL;
    }

• 若當前索引為 "null"，代表這個節點不存在，遞迴結束並 i+1。
• 使用傳址 int& i 來跟蹤當前遍歷的位置。

---

    Node* node = new Node(stoi(preorder[i]));
    i += 1;
    node->left = buildTrees(preorder, i);
    node->right = buildTrees(preorder, i);
    return node;
}

• 否則轉為整數，建立新節點。
• 遞迴建構左子與右子。

---

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

標準中序遍歷：左 → 根 → 右。

---

int main(){
    int n;
    vector<string> v = {};
    cin >> n;

讀入節點總數（含 "null"）。

---

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

讀入完整的先序序列，每個元素為數字或 "null"。

---

    int i = 0;
    Node* root = buildTrees(v, i);

從第 0 個元素開始重建樹。

---

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

執行中序遍歷並存入 s 向量。

---

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

正確格式輸出結果（用空格分隔，不多空格）。

---

🖼️ 示意圖（以範例 1 為例）

先序輸入：5 3 null null 7 null null

建構 BST：
        5
       / \
      3   7

中序遍歷：左（3）→ 根（5）→ 右（7）

➡️ 輸出：3 5 7

---

⏱️ 時間與空間複雜度

• 時間複雜度：O(n)，每個節點處理一次。
• 空間複雜度：O(n)，包含遞迴棧與輸出結果。

---

✅ 小結

• 這題難點在於理解「完全先序遍歷」與如何用遞迴重建樹。
• 建構後用標準中序遍歷即可得到答案。
• 本題是結合樹結構構建 + 遞迴遍歷的典型題，常見於面試與競賽訓練中。