1650. Lowest Common Ancestor of a Binary Tree III

Lowest Common Ancestor of a Binary Tree III

本題給定二元樹中的兩個節點 p 與 q，每個節點除了 left、right 子節點指標外，還有一個 parent 指標指向其父節點。目標是找出這兩個節點的最低公共祖先（Lowest Common Ancestor, LCA）。

核心洞察：轉化為連結串列交叉點問題

由於每個節點都有 parent 指標，從任意節點往上走（不斷取 parent）最終都會到達根節點（parent == nullptr）。因此，從 p 到根的路徑，以及從 q 到根的路徑，構成了兩條以根節點為終點的鏈。

這與 **LC 160《兩條連結串列的交叉點》**完全同構：

• 把「從 p 不斷走 parent」視為遍歷一條連結串列
• 把「從 q 不斷走 parent」視為遍歷另一條連結串列
• 兩條鏈在 LCA 處「交匯」，之後的路徑（直到根）完全相同

雙指標技巧

設兩個指標 a = p、b = q，同步向上移動：

1. 每一步，a 走向 a->parent；b 走向 b->parent
2. 當 a 到達 nullptr（即走過根節點之後），將 a 重定向到 q（切換到另一條鏈的起點）
3. 同理，當 b 到達 nullptr，將 b 重定向到 p
4. 當 a == b 時，即為 LCA

為什麼這樣能收斂？

設 p 到 LCA 的距離為 d1，q 到 LCA 的距離為 d2，LCA 到根的距離為 d3。

• a 指標的路徑長度：d1 + d3 + d2（走完 p→根，再從 q 走到 LCA）
• b 指標的路徑長度：d2 + d3 + d1（走完 q→根，再從 p 走到 LCA）

兩者總步數相同（均為 d1 + d2 + d3），因此兩指標必然同時抵達 LCA，無需額外空間儲存路徑。

特殊情形

若 p 本身就是 q 的祖先（或反之），兩指標同樣能正確收斂：其中一個指標會在對方切換鏈之前就先到達該節點。

時間複雜度：O(h)

設樹的高度為 h（即根到最深葉節點的距離）。

• 設 p 到 LCA 的距離為 d1，q 到 LCA 的距離為 d2，LCA 到根的距離為 d3。
• 兩個指標各自走的總步數均為 d1 + d2 + d3。
• 其中 d1, d2, d3 皆不超過 h，故總步數 ≤ 3h，即 O(h)。
• 在平衡二元樹中 h = O(log n)；最壞情況（退化為鏈）h = O(n)。

空間複雜度：O(1)

只使用了兩個指標 a 與 b，不依賴遞迴堆疊，也不需要額外的雜湊表或陣列，空間消耗為常數。

與 HashSet 方法相比，雙指標法在空間上具有明顯優勢（O(1) vs O(h)），在 Meta 面試中是首選解法。

方法一：HashSet 儲存祖先路徑（O(h) 時間，O(h) 空間）

思路：先從 p 出發，沿 parent 指標一路走到根，將途中每個節點存入一個 unordered_set；再從 q 出發向上走，第一個出現在集合中的節點即為 LCA。

Node* lowestCommonAncestor(Node* p, Node* q) {
    unordered_set<Node*> ancestors;
    while (p != nullptr) {
        ancestors.insert(p);
        p = p->parent;
    }
    while (!ancestors.count(q)) {
        q = q->parent;
    }
    return q;
}

分析：

• 時間複雜度 O(h)，空間複雜度 O(h)（集合大小最多為樹高）。
• 實作直觀，容易理解，適合快速寫出第一版解。
• 缺點：需要額外的 O(h) 空間；在節點數量極大時，記憶體壓力比雙指標法高。

方法二：計算深度後同步上移（O(h) 時間，O(1) 空間）

思路：先分別計算 p 和 q 到根的深度（步數）dp 與 dq；讓較深的那個節點先上移 |dp - dq| 步，使兩節點在同一深度；再同步向上移動，直到兩節點相遇。

此方法與經典「兩條長度不同連結串列找交叉點」的補齊長度做法等價，同樣是 O(1) 空間，但程式碼比雙指標法稍長。

首選解法

雙指標法（主解）程式碼最簡潔（5 行核心邏輯），且空間最優，是 Meta 面試中最推薦的寫法。HashSet 方法作為備用，在需要快速實作或溝通思路時可先提出，再優化到雙指標。

延伸問題

1. 找 k 個節點的最低公共祖先（Meta 變體） 若輸入從兩個節點擴展為一個節點陣列 vector<Node*> nodes（k 個節點），如何找出它們的 LCA？ 提示：可利用 HashSet 逐步縮減——先求前兩個節點的 LCA，再以結果與第三個節點求 LCA，依此類推，總時間複雜度 O(k · h)。

2. 輸入驗證與無效輸入處理（Meta 面試常問） 若 p 或 q 不存在於同一棵樹中（例如指標來自不同樹），雙指標法會進入無窮迴圈。實際系統中應如何防禦？ 提示：可在走訪時記錄已訪問節點，或限制迴圈最大步數（2 * max_depth），超過則回傳 nullptr 表示無效輸入。

3. 無 parent 指標時的對比（LC 236） 本題因有 parent 指標得以用 O(1) 空間解決；若退回 LC 236（無 parent），則需要遞迴 DFS，空間複雜度回到 O(h)（遞迴堆疊）。兩題對比是理解樹結構與空間權衡的好例子，面試中可主動提及展示系統思維。