The solution is pretty straightforward to understand. As we process an internal node (a non-leaf node), we decrease the sum by the node’s value and call the hasPathSum
function on the node’s children. Whenever we encounter a leaf node, if the remaining sum is equal to leaf node’s value then we have found such a path so we return true. Beware of the other terminating condition - we have to return false when node is null.
bool hasPathSum(TreeNode* node, int remainingSum) {
if (node==NULL)
return false;
if (!node->left && !node->right && node->val==remainingSum) return true;
return hasPathSum(node->left, remainingSum-node->val) || hasPathSum(node->right, remainingSum-node->val);
}
Time complexity: O(n) where n is the number of nodes in tree
Space complexity: O(h) where h is the height of tree