Root-to-Leaf Target Total
EasyTrees
Problem
A hiking map is a binary tree whose nodes carry an elevation change. A trail starts at the root and ends at a leaf (a node with no children).
Given the root and an integer target, return true if some root-to-leaf trail has values summing exactly to target.
Example 1
- Input:
- root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], target = 22
- Output:
- true
5 + 4 + 11 + 2 = 22.
Example 2
- Input:
- root = [1, 2, 3], target = 5
- Output:
- false
The two trails sum to 3 and 4.
Constraints
- 0 ≤ number of nodes ≤ 5000
- -1000 ≤ node.val ≤ 1000
- -10^6 ≤ target ≤ 10^6
Hint
Show the first hint
Carry information down the tree instead of collecting whole trails.
Walkthrough
How to approach it
01Clarify before coding
- Must the trail end at a leaf? Yes: stopping at an inner node does not count, see [1, 2] with target 1.
- Empty tree? There are no trails, so false even for target 0.
- Negative values? Yes, so you cannot prune when the running sum exceeds target.
02Brute force
Enumerate every root-to-leaf trail as a list, sum each list and compare.
Cost: O(n · h) time and memory because every trail is rebuilt from scratch.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.