:type root: TreeNode
    :type sum: int
    :rtype: bool

def has_path_sum(root, sum):
    """
    :type root: TreeNode
    :type sum: int
    :rtype: bool
    """
    if root is None:
        return False
    if root.left is None and root.right is None and root.val == sum:
        return True
    sum -= root.val
    return has_path_sum(root.left, sum) or has_path_sum(root.right, sum)