Tree — 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.
Note: A leaf is a node with no children.
Given the below binary tree and
sum = 22,
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path
5->4->11->2 which sum is 22.
Solution is exactly like this algorithm. Try and understand the iterative part.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
sum_to_end = 0
stack = [(root, 0)]
found = False
while stack and not found:
node, current_value = stack.pop()
current_value = current_value + node.val
if not node.left and not node.right:
if current_value == sum:
found = True
current_value = 0else: