Path Sum 這是一題經典的二元樹問題，測試我們對樹的遍歷與遞迴的理解。

題目：

給定一個二元樹的根節點 root 和一個整數目標值 targetSum，判斷該樹是否存在一條從根節點到葉子節點的路徑，使得這條路徑上所有節點值的總和等於目標值。

• 葉子節點是指沒有子節點的節點。

範例：

範例 1：

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
輸出：true
解釋：存在一條路徑 5 -> 4 -> 11 -> 2，其總和為 22。

範例 2：

輸入：root = [1,2,3], targetSum = 5
輸出：false

範例 3：

輸入：root = [], targetSum = 0
輸出：false

實作：

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {

        if (!root) return false;

        if (!root->left && !root->right) {
            return targetSum == root->val;
        }

        int remainingSum = targetSum - root->val;
        return hasPathSum(root->left, remainingSum) || hasPathSum(root->right, remainingSum);
    }
};

參考：
#112. Path Sum