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.
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.
Source
# 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 has_path_sum(root, amount):
"""Recursive approach."""
if root is None:
return False
if root.left is None and root.right is None:
return root.val == amount
if root.left is None: # Technically
return has_path_sum(root.right, amount-root.val) # this part is not needed
if root.right is None: # but
return has_path_sum(root.left, amount-root.val) # speed up the algo a tiny bit
return (has_path_sum(root.left, amount-root.val) or has_path_sum(root.right, amount-root.val))
Solve it both recursively and iteratively.
def has_path_sum(root, amount):
"""Iterative approach using BFS traversal with a list."""
if not root:
return False
queue = [(root, 0)]
for (node, prev_sum) in queue:
if not node:
continue
curr_sum = prev_sum + node.val
if not node.left and not node.right and curr_sum == amount: # only check for leaf nodes
return True
queue.extend([(node.left, curr_sum), (node.right, curr_sum)])
return False
def has_path_sum(root, amount):
"""Iterative approach using BFS traversal with a deque (slower)."""
if not root:
return 0
queue = deque()
queue.append((root, 0))
while queue:
node, prev_sum = queue.popleft()
if not node:
continue
curr_sum = prev_sum + node.val
if not node.left and not node.right and curr_sum == amount: # only checkfor leaf nodes
return True
queue.extend([(node.left, curr_sum), (node.right, curr_sum)])
return False