LeetCode: HasPathSum

hasPathSum.cpp

/**
 * Things to ask in an interview: Can sum ever be zero
 * Time: O(n) (n = number of nodes)
 */

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