Easy Recursive Descent Advanced Trees
In plain English: Check if any path from the root to a leaf adds up to a given target number.
Subtract the current node's value from the target as you descend. At a leaf, check if the remaining target is zero.
Prompt
Given a binary tree and a target sum, determine if there is a root-to-leaf path that sums to the target.
Try to write it from scratch before scrolling down.
Solution
def has_path_sum(root, target):
if not root:
return False
target -= root.val
if not root.left and not root.right:
return target == 0 # leaf: check if sum matches
return has_path_sum(root.left, target) or has_path_sum(root.right, target)
# Test: tree [5,4,8,11,null,13,4,7,2,null,null,null,1], target=22 => True
# Path: 5->4->11->2