🧠 一、知識點解析

1. 層序遍歷重建二元搜尋樹（BST）

• 「層序遍歷 + null」能唯一還原一棵二叉樹。
• 使用 queue 模擬逐層建構的過程。

2. 二元搜尋樹性質

• 對於任一節點：

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

這性質允許我們在查詢時剪枝：

• 若 root->val < low，只需查右子樹
• 若 root->val > high，只需查左子樹
• 若在範圍內，兩邊都查

3. 區間和查詢（Range Sum）

• 對 BST 遞迴走訪，在指定區間 [low, high] 累加符合條件的節點值。

---

🧾 二、逐行程式碼講解

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

🔹 引入必要標頭與命名空間。

---

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

🔹 定義二元樹節點，包含值與左右子指標。

---

TreeNode* buildTree(vector<string>& lll){
    if(lll.size() == 0 || lll[0] == "null"){
        return NULL;
    }

🔹 若樹為空（即第一個是 null），直接返回空指標。

---

    queue<TreeNode*> qqq = {};
    TreeNode* root = new TreeNode(stoi(lll[0]));
    qqq.push(root);
    int i = 1;

🔹 使用 queue 按層建立節點。根節點先建好。

---

    while(i < lll.size() && !qqq.empty()){
        TreeNode* node = qqq.front();
        qqq.pop();

🔹 用 queue 取出目前父節點，準備處理其左右子節點。

---

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

🔹 若下一個不是 "null"，建立左子節點並入隊。

---

        if(i < lll.size() && lll[i] != "null"){
            node->right = new TreeNode(stoi(lll[i]));
            qqq.push(node->right);
        }
        i++;
    }
    return root;
}

🔹 同理建立右子節點。完成後返回樹根。

---

void rangeSum(TreeNode* root, int& sum, int& low, int& high){
    if(root == NULL) return;

🔹 遞迴函式，若節點為空則結束。

---

    if(root->val < low){
        rangeSum(root->right, sum, low, high);
    } else if(root->val > high){
        rangeSum(root->left, sum, low, high);
    } else {
        sum += root->val;
        rangeSum(root->left, sum, low, high);
        rangeSum(root->right, sum, low, high);
    }
}

🔹 根據 BST 特性剪枝：

• 小於 low → 查右
• 大於 high → 查左
• 否則 → 加入 sum 並遞迴兩邊

---

int main(){
    int n;
    cin >> n;
    vector<string> lll = {};
    string ttt;
    for(int i = 0; i < n; i++){
        cin >> ttt;
        lll.push_back(ttt);
    }

🔹 輸入層序遍歷資料。

---

    int low,high;
    cin >> low >> high;
    TreeNode* root = buildTree(lll);

🔹 輸入區間範圍，並還原整棵 BST。

---

    int ans = 0;
    rangeSum(root, ans, low, high);
    cout << ans;
    return 0;
}

🔹 計算區間總和並輸出。

---

🌲 三、示意圖（範例一）

輸入：

7
10 5 15 3 7 null 18
7 15

對應 BST 結構：

        10
       /  \
      5    15
     / \     \
    3   7     18

落在區間 [7, 15] 的節點：7、10、15 總和：32 ✅

---

✅ 四、完整程式碼

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

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

TreeNode* buildTree(vector<string>& lll){
    if(lll.size() == 0 || lll[0] == "null"){
        return NULL;
    }

    queue<TreeNode*> qqq = {};
    TreeNode* root = new TreeNode(stoi(lll[0]));
    qqq.push(root);
    int i = 1;

    while(i < lll.size() && !qqq.empty()){
        TreeNode* node = qqq.front();
        qqq.pop();

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

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

    return root;
}

void rangeSum(TreeNode* root, int& sum, int& low, int& high){
    if(root == NULL) return;
    if(root->val < low){
        rangeSum(root->right, sum, low, high);
    } else if(root->val > high){
        rangeSum(root->left, sum, low, high);
    } else {
        sum += root->val;
        rangeSum(root->left, sum, low, high);
        rangeSum(root->right, sum, low, high);
    }
}

int main(){
    int n;
    cin >> n;
    vector<string> lll = {};
    string ttt;
    for(int i = 0; i < n; i++){
        cin >> ttt;
        lll.push_back(ttt);
    }

    int low, high;
    cin >> low >> high;

    TreeNode* root = buildTree(lll);

    int ans = 0;
    rangeSum(root, ans, low, high);
    cout << ans;
    return 0;
}

---

🔁 五、流程圖（文字版）

開始
 ↓
讀入 n 與 n 個節點（含 "null"）
 ↓
呼叫 buildTree() → 用 queue 還原層序二元樹
 ↓
輸入區間 [low, high]
 ↓
呼叫 rangeSum()：
    若節點為 NULL → 返回
    若節點值 < low → 遞迴右子樹
    若節點值 > high → 遞迴左子樹
    否則：
        將節點值加進 sum
        遞迴左右子樹
 ↓
輸出 sum
 ↓
結束