Leetcode: 112. Path Sum

问你这棵树有没有哪条从root到leaf的路径，是满足路径上的节点加总起来等於targetsum的？

思路

呃，用Traversal，然後在找到leaf的时候，检查此时的sum有没有满足，有就return true，没有就要往上扣回到有另外一条路的部分

程序码

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        return findPath(root, targetSum, 0);
    }
private:
    bool findPath(TreeNode* curr, int targetSum, int currSum) {
        if (curr == NULL)
            return false;
        
        if (curr->left == NULL && curr->right == NULL)
            return currSum + curr->val == targetSum? true:false;
        
        return findPath(curr->left, targetSum, currSum+curr->val) || \
              findPath(curr->right, targetSum, currSum+curr->val);
    }
};

恩

只要在判断时没有真的加上去，就不用处理扣回来的问题

参考：
https://leetcode.com/problems/path-sum/discuss/1515918/C%2B%2B-beats-88-DFS