📘 一、知識點解析

✅ 1. 完全先序遍歷 + 還原二叉樹

• 所謂「完全先序遍歷」是指先序遍歷過程中不省略空節點（用 "null" 表示），所以能唯一還原出原始結構。
• 還原過程可以用遞迴處理：遇到 "null" 就返回 NULL，否則建一個節點後遞迴處理其左右子樹。

✅ 2. 樹的高度定義

• 樹的「高度」定義為：從根節點到最深葉子之間邊的數量。
• 若使用遞迴函數返回的是節點的深度（從根開始數節點個數），那麼高度 = 節點數 - 1。

---

🔍 二、逐行程式碼講解

#include<iostream>
#include<vector>

🔹 引入標準輸入輸出與動態陣列容器 vector。

using namespace std;

🔹 使用 std 命名空間，方便後續書寫。

---

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

🔹 定義一個基本二元樹結構 TreeNode：

• val 為節點值
• left、right 指向左右子樹

---

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

🔹 遞迴建樹：

• 如果目前位置超出範圍或是 "null"，表示該處為空節點。

---

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

🔹 否則建立新節點，再遞迴構建左子樹與右子樹。

---

int getHeight(TreeNode* root){
    if(root == NULL){
        return 0;
    }

🔹 若節點為空，返回 0。

---

    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return 1 + (leftHeight > rightHeight ? leftHeight: rightHeight);
}

🔹 否則高度為左右子樹最大高度 +1（此 +1 是「節點數」，非邊數）。

---

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

🔹 輸入部分，讀取先序遍歷序列。

---

    int t = 0;
    TreeNode* root = buildTree(preorder, t);
    int height = getHeight(root);
    cout << height - 1;
    return 0;
}

🔹 呼叫建樹函數與高度函數。最後輸出高度需減 1（節點數 - 1 = 邊數）。

---

🌲 三、示意圖說明

以範例 1 2 null null 3 4 null null null 為例，樹結構如下：

        1
       / \
      2   3
         /
        4

各節點對應邊數：

• 根到 4 路徑為：1 → 3 → 4 → 共 2 條邊。

---

🧭 四、流程圖（文字形式）

開始
 ↓
輸入 n 與 n 個節點（含 "null"）
 ↓
建立建樹索引 idx = 0
 ↓
遞迴 buildTree：
    若節點為 "null"，返回 NULL
    否則建立節點，build 左子樹，再 build 右子樹
 ↓
遞迴 getHeight：
    若節點為 NULL，返回 0
    否則返回 max(左高, 右高) + 1
 ↓
輸出 高度 - 1（轉為邊數）
 ↓
結束

---

✅ 五、完整程式碼

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

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

TreeNode* buildTree(vector<string>& preorder, int & idx){
    if(idx >= preorder.size() || preorder[idx] == "null"){
        idx++;
        return NULL;
    }
    TreeNode* root = new TreeNode(stoi(preorder[idx]));
    idx++;
    root->left = buildTree(preorder, idx);
    root->right = buildTree(preorder, idx);
    return root;
}

int getHeight(TreeNode* root){
    if(root == NULL){
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return 1 + max(leftHeight, rightHeight);
}

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

    int idx = 0;
    TreeNode* root = buildTree(preorder, idx);
    int height = getHeight(root);
    cout << height - 1 << endl;
    return 0;
}