TreeNode(val, left=None, right=None) is in the starter. Keep it.
A root-to-leaf path starts at the root and follows children down until it reaches a leaf, a node with no children at all. Write path_sum(root, target) -> list[list[int]] that returns every root-to-leaf path whose values add up to target. Each path is the list of its values from the root down. Return the paths in any order; an empty tree has none.
# 6
# / \
# 2 9
# / \ / \
# 4 5 -2 3
# / \
# 1 7
path_sum(root, 13) # [[6, 2, 4, 1], [6, 2, 5]]
6 + 9 + (−2) is also 13, but −2 has a child (7), so that path doesn't end at a leaf. Going on to 7 makes 20.
path_sum(from_list([1, 2]), 1) # []: the root alone isn't a leaf, it has the child 2
path_sum(TreeNode(-4), -4) # [[-4]]: a lone root is a leaf
path_sum(None, 0) # []
- Up to 5,000 nodes, at most 500 levels deep. Values are between
-1000and1000,targetbetween-10^6and10^6. - Values may be negative, so a running sum that passes
targetcan still come back to it: don't stop early.
Show hint
Walk down the tree keeping the current path in one list: append a node on the way in and pop it on the way out. When you reach a leaf whose path adds up to target, save a copy of the list.