/*
 * 演算法 / 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;
}