🧠 一、知識點解析

1. 二元樹建構（字串節點名）

• 節點名稱是唯一字串，需要使用 unordered_map<string, TreeNode*> 來建立及查找節點。
• 使用 unordered_set<string> 來記錄所有子節點，以從中找出唯一的「根節點」（沒有被作為任何其他節點的子節點）。

2. 最近共同祖先（LCA）

• 定義：在一棵樹中，同時為節點 a 與 b 的祖先中，離兩者最近的那一個。

• 標準解法：遞迴後序遍歷

  • 如果當前節點等於 a 或 b，回傳自身
  • 從左右子樹遞迴查詢是否有 a/b 存在
  • 若 a 在左，b 在右（或反之），此節點即為最近共同祖先
  • 若都在同一側，返回該側結果

---

🧾 二、逐行程式碼講解

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

🔹 引入所需標頭，使用 unordered_map 快速儲存與查找節點。

---

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

🔹 每個節點以字串命名，含有左右子樹指標。

---

🔨 構建樹結構

int n;
cin >> n;

unordered_map<string, TreeNode*> keyToNode = {};
unordered_set<string> hasParentNodes = {};

🔹 宣告字典與集合：

• keyToNode：節點名字 → 節點指標
• hasParentNodes：記錄有父節點的所有子節點，用來找根節點

---

for(int i = 0; i < n; i++){
    string parent, left, right;
    cin >> parent >> left >> right;

🔹 每筆資料輸入一組父子關係（可能為 null）

---

    TreeNode* parentNode = keyToNode.count(parent) ? keyToNode[parent] : (keyToNode[parent] = new TreeNode(parent));

🔹 若父節點尚未出現，建立新節點；否則使用已存在的節點指標。

---

    if(left != "null"){
        TreeNode* leftNode = keyToNode.count(left) ? keyToNode[left] : (keyToNode[left] = new TreeNode(left));
        parentNode->left = leftNode;
        hasParentNodes.insert(left);
    }
    if(right != "null"){
        TreeNode* rightNode = keyToNode.count(right) ? keyToNode[right] : (keyToNode[right] = new TreeNode(right));
        parentNode->right = rightNode;
        hasParentNodes.insert(right);
    }
}

🔹 分別處理左右子節點，建立連結並記錄子節點。

---

🔍 找出根節點

TreeNode* root = NULL;
for(auto it = keyToNode.begin(); it != keyToNode.end(); it++){
    if(hasParentNodes.find(it->first) == hasParentNodes.end()){
        root = it->second;
        break;
    }
}

🔹 若某節點名稱不曾作為他人子節點，即為根節點。

---

🧮 實作 LCA 遞迴

TreeNode* LCA(TreeNode* node, string& a, string& b){
    if(node == NULL) return NULL;
    if(node->val == a || node->val == b) return node;
    
    TreeNode* inLeft = LCA(node->left, a, b);
    TreeNode* inRight = LCA(node->right, a, b);

    if(inLeft && inRight) return node;
    return inLeft ? inLeft : inRight;
}

🔹 遞迴查詢左右子樹：

• 如果兩邊都找到了節點，當前節點是最近共同祖先。
• 若只有一邊找到，返回該側。
• 若兩邊都沒找到，返回 NULL。

---

string a, b;
cin >> a >> b;

TreeNode* lca = LCA(root, a, b);
cout << lca->val << endl;

🔹 讀入查詢的兩人，呼叫 LCA 並輸出答案。

---

🌳 三、範例結構示意圖

輸入：

7
A B C
B D E
C F G
D null null
E null null
F null null
G null null
D G

建構出樹：

        A
       / \
      B   C
     / \ / \
    D  E F  G

• D 和 G 的最近共同祖先是 A ✅

---

✅ 四、完整程式碼

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>

using namespace std;

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

TreeNode* LCA(TreeNode* node, string& a, string& b){
    if(node == NULL) return NULL;
    if(node->val == a || node->val == b) return node;

    TreeNode* inLeft = LCA(node->left, a, b);
    TreeNode* inRight = LCA(node->right, a, b);

    if(inLeft && inRight) return node;
    return inLeft ? inLeft : inRight;
}

int main(){
    int n;
    cin >> n;
    
    unordered_map<string, TreeNode*> keyToNode;
    unordered_set<string> hasParentNodes;
    
    for(int i = 0; i < n; i++){
        string parent, left, right;
        cin >> parent >> left >> right;

        TreeNode* parentNode = keyToNode.count(parent) ? keyToNode[parent] : (keyToNode[parent] = new TreeNode(parent));
        
        if(left != "null"){
            TreeNode* leftNode = keyToNode.count(left) ? keyToNode[left] : (keyToNode[left] = new TreeNode(left));
            parentNode->left = leftNode;
            hasParentNodes.insert(left);
        }
        if(right != "null"){
            TreeNode* rightNode = keyToNode.count(right) ? keyToNode[right] : (keyToNode[right] = new TreeNode(right));
            parentNode->right = rightNode;
            hasParentNodes.insert(right);
        }
    }

    TreeNode* root = NULL;
    for(auto it = keyToNode.begin(); it != keyToNode.end(); it++){
        if(hasParentNodes.find(it->first) == hasParentNodes.end()){
            root = it->second;
            break;
        }
    }

    string a, b;
    cin >> a >> b;

    TreeNode* lca = LCA(root, a, b);
    cout << lca->val << endl;

    return 0;
}

---

🔁 五、流程圖（文字版本）

開始
 ↓
輸入 n
 ↓
重複 n 次：
    讀入 parent left right
    建立節點並建立父子關係
    記錄所有被當作子節點出現過的名稱
 ↓
遍歷所有節點：
    找出沒有被記錄為子節點的 → root
 ↓
輸入 a 與 b
 ↓
遞迴 LCA：
    若當前節點為 a 或 b，返回當前
    否則向左右遞迴查詢
    若左右皆非空 → 回傳當前
    若只有一側非空 → 回傳該側
 ↓
輸出最近共同祖先名稱
 ↓
結束