Path Sum

Easy#112top-down

You get the root of a binary tree and a target number. Say whether some path from the root down to a leaf, a node without children, adds up to the target. Our tree: 6 with children 4 and 3; 4 has only a right child 5, and 3 has children 1 and 2. Target 10 — the answer is true: 6 → 3 → 1. 6 → 4 also makes 10, but 4 is not a leaf.

112 Path SumWalkthrough · 1×

Example: check whether some root-to-leaf path adds up to 10: each call takes off its own value and passes what is left down.

target = 10beside: restnone643512call stacktop on the right6
not visited yeton the path, waitingcurrent callreturned truereturned false

6 is a node, not none: 10 is still to collect

01/30
restart · back · play · step
Speed
1function hasPathSum(node, target):
2 if node is none:
3 return false
4 rest = target - node.val
5 if node.left is none and node.right is none:
6 return rest == 0 // only a leaf ends a path
7 if hasPathSum(node.left, rest):
8 return true
9 return hasPathSum(node.right, rest)
state
node
6
target
10
rest
–
click a step to go back

← → step · space play/pause

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.