236. Lowest Common Ancestor of a Binary Tree

題目 / Problem

中文： 給定一棵二元樹，以及樹中的兩個節點 p 和 q，找出它們的「最近公共祖先」(LCA)。根據維基百科的定義：最近公共祖先是指樹 T 中「同時擁有 p 和 q 作為後代」的最低節點（我們允許一個節點是它自己的後代）。換句話說，我們要找那個「往下能同時走到 p 又能走到 q」的最深的分岔點。

English: Given a binary tree and two nodes p and q in it, find their Lowest Common Ancestor (LCA). By the Wikipedia definition, the LCA is the lowest node in the tree that has both p and q as descendants, where we allow a node to be a descendant of itself. In plain words: the deepest node from which you can walk down and reach both p and q.

Constraints / 限制： - 節點數量在 [2, 10^5] 範圍內 / Number of nodes is in [2, 10^5]. - -10^9 <= Node.val <= 10^9，且所有 Node.val 皆唯一 / all values are unique. - p != q，且 p、q 一定存在於樹中 / p and q are guaranteed to be in the tree.

Worked example / 範例：

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3

樹長這樣 / The tree looks like:

          3
        /   \
       5     1
      / \   / \
     6   2 0   8
        / \
       7   4

5 在左子樹、1 在右子樹，它們最低的共同祖先就是根 3。 5 is in the left subtree and 1 is in the right subtree, so their lowest common ancestor is the root 3.

名詞解釋 / Glossary

• 二元樹 / Binary tree：每個節點最多有兩個子節點（left 和 right）的樹狀結構。/ A tree where each node has at most two children, called left and right.
• 節點 / Node：樹中的一個元素，這裡每個節點含一個整數 val 以及指向左右子節點的指標。/ One element of the tree; here each holds an integer val and pointers to its two children.
• 祖先 / Ancestor：從某節點往上（往根方向）路徑上遇到的所有節點；反過來說，該節點是它們的「後代 / descendant」。/ Any node on the upward path toward the root; conversely that node is their descendant.
• 後代是自己 / A node is a descendant of itself：定義上允許把一個節點當成自己的後代，所以若 p 本身就是 q 的祖先，答案就是 p。/ The definition lets a node count as its own descendant, so if p is itself an ancestor of q, the answer is p.
• DFS（深度優先搜尋）/ Depth-First Search：一種走訪策略，先深入走到底再回頭。這裡我們用遞迴 / recursion（函式呼叫自己）來實現，天然地先處理子樹再處理父節點。/ A traversal that goes deep first, then backtracks; we implement it with recursion so subtrees are handled before their parent.
• 遞迴 / Recursion：函式呼叫自己來處理更小的子問題，每次呼叫都有自己的區域變數。/ A function calling itself on a smaller sub-problem, each call keeping its own local variables.
• 指標 / Pointer（C）：儲存「某塊記憶體位址」的變數；root->left 表示「順著位址找到 root 這個結構的 left 欄位」。NULL 代表「不指向任何東西」（空）。/ A variable holding a memory address; root->left follows the address to read a field, and NULL means "points to nothing".

思路

先想最直覺的暴力法：對每個節點，我都去它的子樹裡確認「p 在不在裡面」、「q 在不在裡面」。若某個節點兩邊都能找到 p 和 q，它就是一個公共祖先；再選最深的那個。但這樣每個節點都要重新掃一遍它的整棵子樹，時間會退化到 O(n²)，對 10^5 個節點太慢。關鍵觀察是：這些「往子樹裡找」的工作其實高度重複，我們可以用一次遞迴後序走訪（先處理子節點、再處理父節點）把它一次算完。定義遞迴函式 lca(node)：如果 node 是空的、或等於 p、或等於 q，就直接回傳 node 本身（因為節點可以是自己的後代，找到目標就回報）。否則遞迴去問左子樹和右子樹。回傳值代表「這棵子樹裡找到了 p 或 q 的話，回報那個目標（或已算出的祖先）」。三種情況：若左、右各自都回傳了非空值，代表 p 和 q 分別落在兩側，那當前 node 就是最近公共祖先，回傳 node；若只有一側非空，就把那一側的結果往上傳（表示兩個目標都在同一側，答案在更深處或就是這個回報值）；若兩側都空就回傳空。因為題目保證 p、q 都存在，這個「第一個看到左右都有回報」的節點必定是正確答案。它只走訪每個節點一次，因此是 O(n)。

Start with the brute-force idea: for each node, search its subtree to check whether p is inside and whether q is inside; a node with both on its side is a common ancestor, and we keep the deepest one. But re-scanning the whole subtree at every node degrades to O(n²), too slow for 10^5 nodes. The key insight is that all this "search the subtree" work is redundant and can be folded into a single post-order recursion (children handled before the parent). Define lca(node): if node is null, or equals p, or equals q, return node itself — because a node may be its own descendant, so finding a target means we report it upward. Otherwise recurse into the left and right children. The return value means "if this subtree contains p or q, report that target (or an already-computed ancestor)". Three cases: if both left and right return non-null, then p and q sit on opposite sides, so the current node is their LCA — return node; if only one side is non-null, pass that side's result upward (both targets are on that side, deeper down, or the result is itself the answer); if both sides are null, return null. Since p and q are guaranteed to exist, the first node that sees non-null from both sides is exactly the answer. Every node is visited once, so it runs in O(n).

逐步走查 / Walkthrough

以 root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 為例。我們追蹤遞迴 lca(node) 的回傳值（回傳「找到的目標節點或已定案的祖先」，NULL 表示沒找到）。表格由最深的呼叫往上排列：

最上層 lca(3) 看到左邊帶回 5、右邊帶回 1，兩者都非空，於是回傳 3，即最終答案。 At the top, lca(3) sees 5 bubbling up from the left and 1 from the right — both non-null — so it returns 3, the final answer.

Solution — C

/*
 * 演算法 / Algorithm:
 * 一次後序 DFS 遞迴。lca(node) 回傳「此子樹中找到的 p 或 q（或已定案的 LCA）」。
 * One post-order DFS. lca(node) returns a found target (or the settled LCA) from this subtree.
 * 若左右子樹各帶回一個非空值，當前節點就是 LCA；否則把非空的那一側往上傳。
 * If both sides return non-null, the current node is the LCA; otherwise pass up the non-null side.
 */

// LeetCode 已定義好這個結構，這裡再寫一次方便閱讀 / LeetCode already defines this struct; shown for clarity.
struct TreeNode {
    int val;                    // 節點值 / the node's integer value
    struct TreeNode *left;      // 指向左子節點的指標 / pointer to the left child
    struct TreeNode *right;     // 指向右子節點的指標 / pointer to the right child
};

struct TreeNode* lowestCommonAncestor(struct TreeNode* root,
                                      struct TreeNode* p,
                                      struct TreeNode* q) {
    // 基底情況：走到空節點就沒東西可找，回傳 NULL（空指標）。
    // Base case: an empty node has nothing to find, return NULL.
    // 若當前節點就是 p 或 q，直接回傳它自己（允許節點是自己的後代）。
    // If this node is p or q, return it directly (a node can be its own descendant).
    if (root == NULL || root == p || root == q)
        return root;

    // 遞迴左子樹：問「左邊有沒有找到 p 或 q？」/ Recurse left: did the left side find p or q?
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);

    // 遞迴右子樹：問「右邊有沒有找到 p 或 q？」/ Recurse right: did the right side find p or q?
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);

    // 左右都非空 → p 與 q 分居兩側 → 當前 root 就是最近公共祖先。
    // Both non-null → p and q are on opposite sides → current root is the LCA.
    if (left != NULL && right != NULL)
        return root;

    // 只有一側非空：把那一側的結果往上回報（另一側是 NULL）。
    // Exactly one side non-null: bubble up that side's result (the other is NULL).
    // 若兩側都是 NULL，這裡也會回傳 NULL，代表這棵子樹什麼都沒找到。
    // If both are NULL, this returns NULL, meaning nothing was found in this subtree.
    return (left != NULL) ? left : right;
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 與 C 版完全相同：一次後序 DFS 遞迴。
 * Identical to the C version: a single post-order DFS recursion.
 * 左右子樹各回報找到的目標；兩側都非空的節點即為 LCA。
 * Each side reports a found target; the node where both sides are non-null is the LCA.
 */

// LeetCode 提供的節點定義 / Node definition provided by LeetCode:
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
// };

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 基底情況：空節點回傳 nullptr；命中 p 或 q 就回傳自己。
        // Base case: empty node returns nullptr; hitting p or q returns itself.
        // nullptr 是 C++ 的空指標（等同 C 的 NULL，但型別更安全）。
        // nullptr is C++'s null pointer (like C's NULL, but type-safe).
        if (root == nullptr || root == p || root == q)
            return root;

        // 遞迴查左、右子樹 / Recurse into left and right subtrees.
        // auto 讓編譯器自動推導型別（這裡是 TreeNode*），少打字也不易寫錯。
        // auto lets the compiler deduce the type (TreeNode* here) — less typing, fewer mistakes.
        auto left  = lowestCommonAncestor(root->left,  p, q);
        auto right = lowestCommonAncestor(root->right, p, q);

        // 左右都找到東西 → p、q 分居兩側 → 當前節點就是 LCA。
        // Both sides found something → p and q split across sides → this node is the LCA.
        if (left && right)          // 指標非空在條件式中視為 true / a non-null pointer is truthy
            return root;

        // 否則回傳非空的那一側；若都空則回傳 nullptr。
        // Otherwise return whichever side is non-null; if both null, return nullptr.
        return left ? left : right;
    }
};

複雜度 / Complexity

• Time: O(n) — n 是樹的節點數。遞迴對每個節點恰好呼叫一次，每次只做常數量的比較與判斷，所以總時間與節點數成正比。/ n is the number of nodes; the recursion visits each node exactly once doing constant work, so time is proportional to the node count.
• Space: O(h) — h 是樹的高度，來自遞迴呼叫堆疊（call stack）。最壞情況樹退化成一條鏈時 h = n，即 O(n)；平衡樹則約為 O(log n)。/ h is the tree height, from the recursion call stack; worst case (a degenerate chain) is O(n), a balanced tree is about O(log n).

Pitfalls & Edge Cases

• 比較的是節點位址，不是值 / Compare node identity, not value. 我們用 root == p 比對「是不是同一個節點」。因為題目保證值唯一，比值也可行，但比指標更直接且與定義一致。/ We compare pointers (root == p) to test node identity; values are unique so comparing values also works, but pointer comparison matches the definition directly.
• 「節點可以是自己的後代」/ A node can be its own descendant. 這正是 root == p || root == q 時立刻回傳的原因：若 p 是 q 的祖先，答案就是 p（見範例 2）。漏掉這條會答錯。/ This is exactly why we return immediately on root == p || root == q: if p is an ancestor of q, the answer is p (Example 2). Missing it gives wrong answers.
• 別忘了回傳「往上傳結果」那一行 / Don't forget to bubble up the found side. 常見錯誤是只在 left && right 時回傳、其他情況回傳 NULL，這會讓已找到的目標「消失」，導致更上層永遠看不到它。/ A common bug is returning a value only when left && right and NULL otherwise, which loses an already-found target so higher levels never see it.
• 不需要處理空樹 / No empty-tree case needed. 限制保證節點數至少為 2 且 p、q 一定存在，因此遞迴必定會找到答案，不會回傳 NULL 給最外層呼叫者。/ Constraints guarantee at least 2 nodes and that p, q exist, so the top-level call always finds an answer and never returns NULL.
• 遞迴深度 / Recursion depth. 對極度不平衡（近乎鏈狀）的 10^5 節點樹，遞迴深度可達 10^5，理論上有堆疊溢位風險；LeetCode 測資通常可通過，但要知道這是遞迴解法的固有限制。/ For a near-chain tree of 10^5 nodes the recursion can go 10^5 deep, a theoretical stack-overflow risk; it passes on LeetCode but is an inherent limit of the recursive approach.