Root-to-leaf path sum
You get the root of a binary tree of integers and an integer target. Call a node a leaf when both its left and its right are None. A root-to-leaf path starts at the root and follows child links down until it stops at a leaf.
Return True if the values on at least one root-to-leaf path add up to exactly target, and False otherwise. A path that stops at a node with children does not count. An empty tree has no paths, so it gives False.
Examples write a tree level by level, left to right, with None where a child is missing.
root = [5, 3, 8, 2, None, 4, 1], target = 10OutputTrueThe path 5, 3, 2 ends at a leaf and adds up to 10.
root = [5, 3, 8, 2, None, 4, 1], target = 13OutputFalseThe three root-to-leaf paths add up to 10, 17 and 14. 5 + 8 is 13, but 8 has children, so that path does not end at a leaf.
root = [], target = 0OutputFalseNo nodes means no paths, not even one that adds up to 0.
0 ≤ number of nodes ≤ 5,000
The tree is at most 900 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
-1,000 ≤ val ≤ 1,000
-106 ≤ target ≤ 106
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.