/*
 * 演算法 / Algorithm:
 *   與 C 版相同：DFS + 遞迴。往下遞減 targetSum，葉子處比對剩餘量。
 *   Same as the C version: DFS with recursion; decrement targetSum going down
 *   and compare the remainder at each leaf.
 */

/**
 * Definition provided by LeetCode / LeetCode 已提供:
 *   struct TreeNode {
 *       int val;
 *       TreeNode *left;
 *       TreeNode *right;
 *   };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        // 空節點：沒有路徑，回傳 false / Null node: no path here, return false.
        // nullptr 是 C++ 的空指標（比 C 的 NULL 更型別安全）。
        // nullptr is C++'s null pointer (more type-safe than C's NULL).
        if (root == nullptr) {
            return false;
        }

        // 葉子判斷：兩個子節點都是 nullptr。
        // Leaf check: both children are nullptr.
        if (root->left == nullptr && root->right == nullptr) {
            // 葉子處：剩餘目標是否剛好等於這個葉子的值。
            // At the leaf: does the remaining target equal this leaf's value?
            return targetSum == root->val;
        }

        // 非葉子：計算傳給子節點的新目標。
        // Internal node: compute the new target to pass to children.
        int remaining = targetSum - root->val;  // 還需湊出的總和 / remaining sum needed

        // 左右子樹任一邊成功即可；|| 會短路以節省計算。
        // Either subtree succeeding is enough; '||' short-circuits to save work.
        return hasPathSum(root->left, remaining) ||
               hasPathSum(root->right, remaining);
    }
};