/*
 * 演算法 / Algorithm:
 *   深度優先搜尋 + 遞迴。每往下一層就從 targetSum 減去目前節點的值，
 *   把「還需要湊多少」傳給子節點；走到葉子時檢查剩餘量是否等於葉子值。
 *   DFS with recursion: subtract each node's value from targetSum as we
 *   descend, then at a leaf check whether the remainder equals the leaf's value.
 */

/**
 * struct TreeNode 由 LeetCode 事先定義好 / Provided by LeetCode:
 *   struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; };
 */
bool hasPathSum(struct TreeNode* root, int targetSum) {
    // 空樹沒有任何路徑，直接回傳 false / An empty tree has no path at all.
    // root == NULL 表示這裡沒有節點（NULL 是「空指標」）。
    // root == NULL means there is no node here (NULL is the "null pointer").
    if (root == NULL) {
        return false;
    }

    // 用 -> 取出指標所指節點的成員 / '->' reads a member through a pointer.
    // 判斷是否為葉子：左右子節點都是空。
    // Check for a leaf: both children are empty.
    if (root->left == NULL && root->right == NULL) {
        // 到了葉子，這條路徑成立當且僅當剩餘目標剛好等於葉子的值。
        // At a leaf, the path works exactly when the remaining target equals this value.
        return targetSum == root->val;
    }

    // 還不是葉子：把「扣掉目前值後的新目標」往下傳給兩邊子樹。
    // Not a leaf yet: pass the reduced target down to both subtrees.
    int remaining = targetSum - root->val;  // 剩餘要湊的量 / sum still needed below

    // 左子樹或右子樹只要有一邊能湊成，就回傳 true。
    // If EITHER the left or the right subtree can make it up, return true.
    // || 是「邏輯或」，只要左邊為 true 就會短路，不再算右邊。
    // '||' is logical OR; if the left is true it short-circuits and skips the right.
    return hasPathSum(root->left, remaining) || hasPathSum(root->right, remaining);
}