LeetCode: Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

---

We can use recursive call to solve this problem. If current node is a leaf node, check its value is equal to the sum. If it not a leaf node, check if its left subtree or right subtree can form sum - node.val

C++ Code:

/*
 * func: has_path_sum
 * goal: to determine if there exists such a path from root to leaf which sum up to the given
 * @param root: root node of the tree
 * @param sum: given sum
 * return: true or false
 */
bool has_path_sum(TreeNode *root, int sum){
    if(root ==  nullptr){
        return false;
    }if(root->left == nullptr && root->right == nullptr){
        return sum == root->val;
    }else{
        return has_path_sum(root->left, sum-root->val) ||
        has_path_sum(root->right, sum-root->val);
    }
}

Python Code:

# func: to determine if there exists such a path from root to leaf which sum up to the given
# @param root: root node of the tree
# @param sum: given sum
# @return True or False
def has_path_sum(root, sum):
    if not root:
        return False
    elif not root.left and not root.right:
        return sum == root.val
    else:
        return has_path_sum(root.left, sum-root.val) or has_path_sum(root.right, sum-root.val)