# 112 - Path Sum

解法一 - Recursion

這題的思路頗單純，可以想像成是一個不斷循環的子問題，從 root 開始不斷呼叫自己這個 function，要注意的有：

1. 回傳條件：當走到 leaf 且 leaf->val == sum 時，就表示這條路徑是符合條件的。如果 root == NULL，表示這條路徑在走到 leaf 時還未滿足條件（不然上一層就已經回傳 true 了），那就 return false。

2. 遞迴的狀態改變：每次呼叫下一次遞迴 function 時，要扣到當前 root->val，這樣就變成求一個完全一樣的子問題

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        if(!root->left && !root->right && sum == root->val) return true;

        return (hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val));
    }
};