📘 題目名稱：二元樹左視圖

🧠 知識點解析

1. 二元樹重建：

   • 根據「完全先序遍歷（包含 null）」重建二元樹。
   • 使用遞迴方法從左到右重建整棵樹。

2. BFS 層序遍歷：

   • 使用佇列（Queue）逐層掃描節點。
   • 每層記錄第 0 個（即最左邊的）節點值。

3. 視圖概念應用：

   • 左視圖為每層第一個被看到的節點。
   • 和右視圖、頂視圖、底視圖類似，都是從不同方向觀察二元樹。

4. 資料結構與演算法基礎：

   • 遞迴建樹
   • 使用 STL 的 queue 做 BFS

🌳 樹形結構說明（範例輸入）

輸入：
13
1 2 4 null null 5 null null 3 null 6 null null

還原後的樹結構：
        1
      /   \
     2     3
    / \     \
   4   5     6

層次結構：
第 1 層：1
第 2 層：2, 3
第 3 層：4, 5, 6

左視圖（每層最左邊的節點）為：
1
2
4

🪜 程式流程圖（文字版）

1. 讀入 n 和先序序列。

2. 遞迴重建二元樹。

3. 使用 BFS 從上至下走訪每一層：

   • 每層第 0 個節點輸出。

4. 結束。

🔍 程式碼逐行解析

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

• 引入標準函式庫，處理輸入、字串、佇列等。

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

• 自訂二元樹節點結構，初始化左右子樹為 nullptr。

TreeNode* buildTree(const vector<string>& preorder, int& index) {
    if (index >= preorder.size() || preorder[index] == "null") {
        index++;
        return nullptr;
    }

• 當遇到 "null" 或超出邊界時，回傳 nullptr。

    TreeNode* node = new TreeNode(stoi(preorder[index++]));
    node->left = buildTree(preorder, index);
    node->right = buildTree(preorder, index);
    return node;
}

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

void printLeftView(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);

• 進行 BFS，初始化佇列，從根節點開始。

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front(); q.pop();
            if (i == 0) cout << node->val << "\n";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
}

• 每一層的第一個節點 i == 0 即為左視圖，將其輸出。

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

    int index = 0;
    TreeNode* root = buildTree(preorder, index);
    printLeftView(root);

    return 0;
}

• 主程式：

  • 讀入節點數與先序序列。
  • 還原二元樹。
  • 輸出左視圖。

💻 完整程式碼

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

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

TreeNode* buildTree(const vector<string>& preorder, int& index) {
    if (index >= preorder.size() || preorder[index] == "null") {
        index++;
        return nullptr;
    }

    TreeNode* node = new TreeNode(stoi(preorder[index++]));
    node->left = buildTree(preorder, index);
    node->right = buildTree(preorder, index);
    return node;
}

void printLeftView(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front(); q.pop();
            if (i == 0) cout << node->val << "\n";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
}

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

    int index = 0;
    TreeNode* root = buildTree(preorder, index);
    printLeftView(root);

    return 0;
}