bool hasPathSumUtil(TreeNode* root, int sum) {

if (!root) return false;

if (root->val == sum && !root->left && !root->right) return true;

return (hasPathSumUtil(root->left, sum - root->val) ||

hasPathSumUtil(root->right, sum - root->val));

}

bool hasPathSum(TreeNode *root, int sum) {

return hasPathSumUtil(root, sum);

}