題目網址：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

題意：給一 BT 和兩 node p 和 q, 找出他們的 lowest common ancestor（LCA）T。

Solution：

想法：利用 DFS, 主要分成以三種情形：

  • 無法在左子樹找到任何 target node, 代表 LCA 不可能在左子樹中, 因此 return 右子樹的結果。
  • 無法在右子樹找到任何 target node, 代表 LCA 不可能在右子樹中, 因此 return 左子樹的結果。
  • 若可分別在左右子樹中找到 target node, 代表 current root 為所求

e.g. 下圖中, root = 1, p = 4, q = 10

  • 以 2 為 root 時進行遞迴:
    • left：return 4
    • right：return 10
  • 以 1 為 root 時進行遞迴:
    • left：return 2 (因為其 left, right 皆非 null)
    • right：return null

➔ 故最後答案為 2

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) {
            return root;
        }

        const auto left = lowestCommonAncestor(root->left, p, q);
        const auto right = lowestCommonAncestor(root->right, p, q);

        if (!left) {
            return right;
        }

        if (!right) {
            return left;
        }

        return root; // left, right 皆非 null, 返回 current root
    }
};
  • time：$O(n)$ ➔ 遍歷整個 BT
  • space：$O(n)$ ➔ 遞迴深度不超過 n