🧠 本題知識點

本題涉及以下幾個資料結構與演算法的知識點：

1. 二元樹重建：根據完全先序遍歷（包含 "null"）還原原始樹結構。
2. 先序遍歷解析：Preorder traversal 的順序為：根節點 → 左子樹 → 右子樹。
3. 層序遍歷（BFS）：使用佇列（Queue）進行逐層訪問，記錄每層節點總和，保留最後一層的總和作為輸出。
4. 字串轉整數：使用 stoi() 處理輸入。
5. 指標與遞迴：樹的構建使用遞迴實現，並利用引用方式追蹤目前遍歷位置。

---

🔍 程式碼逐行解析

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

• 引入標準函式庫，包括輸入輸出、動態陣列、佇列、數學。

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

• 定義二元樹節點，包含一個整數值 val 和左右子樹指標。

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

• 遞迴建樹的終止條件：若讀到 "null" 或超出邊界，返回空指標。

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

• 建立新節點，並遞迴建構左子樹與右子樹。

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

• 讀取輸入大小，建立字串陣列儲存先序遍歷資料。

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

• 將每一個字串輸入讀入 vector。

    int c = 0;
    Node* root = buildTrees(preorder, c);

• 開始從第 0 個位置建樹。

    queue<Node*> qqq = {};
    qqq.push(root);

• 使用佇列進行層序遍歷。

    int deep_size = 0;

• 記錄最後一層（最深層）的節點總和。

    while(!qqq.empty()) {
        int level_sum = 0;
        int size = qqq.size();

• 每次進入 while 代表一層。

        for(int i = 0; i < size; i++) {
            Node* node = qqq.front();
            qqq.pop();
            level_sum += node->val;
            if(node->left) qqq.push(node->left);
            if(node->right) qqq.push(node->right);
        }

• 對當前層的每個節點：

  • 計算總和
  • 加入下一層子節點

        deep_size = level_sum;
    }

    cout << deep_size << endl;
    return 0;
}

• 每層更新 deep_size，直到最深層。最終輸出結果。

---

🌳 樹形結構示意圖

輸入：

1 2 4 null null 5 null null 3 null 6 null null

所還原的二元樹：

        1
      /   \
     2     3
    / \     \
   4   5     6

層序遍歷（BFS）分層為：

第 1 層：1
第 2 層：2, 3
第 3 層：4, 5, 6 ← 最深層

---

🔁 程式邏輯流程圖（文字版）

1. 讀入 n 和先序序列。

2. 使用 buildTrees() 還原樹。

3. 利用 Queue 做 BFS：

   • 每層更新節點總和 level_sum
   • 保留最後一次的 level_sum 為 deep_size

4. 輸出 deep_size

---

✅ 輸出說明

對於輸入：

13
1 2 4 null null 5 null null 3 null 6 null null

最深層節點為：4, 5, 6 總和為：4 + 5 + 6 = 15

---

💻 完整程式碼

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

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;
    }
    Node* node = new Node(stoi(preorder[i]));
    i += 1;
    node->left = buildTrees(preorder, i);
    node->right = buildTrees(preorder, i);
    return node;
}

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

    int c = 0;
    Node* root = buildTrees(preorder, c);

    queue<Node*> qqq;
    qqq.push(root);
    int deep_sum = 0;

    while(!qqq.empty()) {
        int size = qqq.size();
        int level_sum = 0;
        for(int i = 0; i < size; i++) {
            Node* node = qqq.front(); qqq.pop();
            level_sum += node->val;
            if(node->left) qqq.push(node->left);
            if(node->right) qqq.push(node->right);
        }
        deep_sum = level_sum;
    }

    cout << deep_sum << endl;
    return 0;
}