236. Lowest Common Ancestor of a Binary Tree

📘 題目敘述

給你一棵二元樹的根節點 root，以及樹中的兩個節點 p 和 q。

請回傳 p 和 q 的最低共同祖先（lowest common ancestor, LCA）。

最低共同祖先的定義是：在樹中同時是 p 和 q 祖先的節點之中，深度最大的那個節點。

題目保證 p 和 q 都存在於這棵樹中，而且 p != q。

條件限制

樹中的節點數量在範圍 [2, 10^5]
-10^9 <= Node.val <= 10^9
所有 Node.val 都互不相同
p != q
p 和 q 都存在於樹中

🧠 解題思路

這題我的想法很特別，用一個 int 紀錄到底走過 p/q 了沒：

1 代表「在這棵子樹裡有找到 p」
10 代表「在這棵子樹裡有找到 q」

所以只要我看這個數字的「個位數 / 十位數」是不是大於 0，我就知道這棵子樹到底有沒有包含 p 或 q。

接著只要某個節點的子樹同時包含 p 和 q，而且這是第一次遇到這種節點，那它就是 LCA，直接記下來當答案。

所有變數

np：我把題目傳進來的 p 存成全域指標，讓遞迴時不用一直帶參數
nq：同理，存 q
first：用來確保答案只會被設定一次
ans：最後要回傳的 LCA 節點指標

🪜 主要流程步驟

1. 用 `check(root)` 回傳「這棵子樹是否包含 p/q」的狀態

我設計 check(root) 回傳一個 int，用位數表示狀態：

回傳 0：這棵子樹沒有 p 也沒有 q
回傳 1：這棵子樹有 p
回傳 10：這棵子樹有 q
回傳 11：這棵子樹同時有 p 和 q

這樣我只要看 k % 10 就知道有沒有 p，看 k / 10 就知道有沒有 q。

2. 在每個節點先判斷「自己是不是 p 或 q」

在 check(root) 裡，我先做：

如果 root == np，先給 k = 1
如果 root == nq，先給 k = 10
否則 k = 0

這代表「光是這個節點本身」有沒有命中 p 或 q。

3. 把左右子樹的狀態加回來，得到整棵子樹的狀態

接著我會做：

k = k + check(root->left) + check(root->right);

這行的意思是：「目前節點 + 左子樹 + 右子樹」三者的狀態全部加總起來。

因為我的設計是 p 用 1、q 用 10，所以加起來後：

只要 k % 10 > 0，代表這整棵子樹裡有 p
只要 k / 10 > 0，代表這整棵子樹裡有 q

4. 第一次遇到同時包含 p 和 q 的節點，就記下來當答案

當我算完 k 之後，我會檢查：

k / 10 > 0 代表有 q
k % 10 > 0 代表有 p

如果兩者都成立，代表這個 root 的子樹同時包含 p 和 q。

而且我用 first 來確保只記第一次：

因為 DFS 是從底下回傳往上推
第一個符合「同時包含 p 和 q」的節點，一定是最深的那個，也就是 LCA

所以我會在第一次遇到時做：

first = false
ans = root

5. 把狀態壓回到 0/1/10/11，避免加總後變成奇怪的數字

因為 k 是三者加總，有可能出現像 12、21 這種值（例如左邊回 11、右邊回 1 之類的狀況），但其實我只在乎「有沒有 p」和「有沒有 q」。

所以我最後會把它壓回四種狀態：

兩者都有 → 回傳 11
只有 q → 回傳 10
只有 p → 回傳 1
都沒有 → 回傳 0

這樣上層節點就能用相同規則繼續判斷。

6. 在 `lowestCommonAncestor` 裡設定全域 p/q，跑 DFS，回傳 ans

我先把 p、q 存到全域的 np、nq，然後呼叫 check(root) 跑完整棵樹。

最後直接回傳 ans。

⏱️ 複雜度

時間複雜度：O(n)
每個節點只會被 DFS 走訪一次，並且每次只做常數次運算。
空間複雜度：O(h)
主要是遞迴呼叫堆疊的深度，h 是樹高。最壞情況（鏈狀樹）會到 O(n)。

💻 程式碼實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *np, *nq;
    bool first = true;
    TreeNode* ans;
    int check(TreeNode* root) { // 0是空,1是p,10是q
        if (root) {
            int k = 0;
            if (root == np) {
                k = 1;
            } else if (root == nq) {
                k = 10;
            }
            k = k + check(root->left) + check(root->right);
            if (first && k / 10 > 0 && k % 10 > 0) {
                first = false;
                ans = root;
            }
            if (k / 10 > 0 && k % 10 > 0) {
                return 11;
            } else if (k / 10 > 0) {
                return 10;
            } else if (k % 10 > 0) {
                return 1;
            } else {
                return 0;
            }
        } else {
            return 0;
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        np = p;
        nq = q;
        check(root);
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/