given a binary tree and a sum determine if the tree has a roottoleaf 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 roottoleaf path 54112 which sum is 22 type root treenode type sum int rtype bool dfs with stack bfs with queue type root treenode type sum int rtype bool dfs with stack bfs with queue popleft
def has_path_sum(root, sum):
    
    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)



def has_path_sum2(root, sum):
    if root is None:
        return False
    stack = [(root, root.val)]
    while stack:
        node, val = stack.pop()
        if node.left is None and node.right is None:
            if val == sum:
                return True
        if node.left is not None:
            stack.append((node.left, val+node.left.val))
        if node.right is not None:
            stack.append((node.right, val+node.right.val))
    return False



def has_path_sum3(root, sum):
    if root is None:
        return False
    queue = [(root, sum-root.val)]
    while queue:
        node, val = queue.pop(0)  
        if node.left is None and node.right is None:
            if val == 0:
                return True
        if node.left is not None:
            queue.append((node.left, val-node.left.val))
        if node.right is not None:
            queue.append((node.right, val-node.right.val))
    return False