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