Why it works
- Every call gets what the path above it still has to collect, so a leaf only has to check that nothing is left: rest == 0.
- The check happens only at a leaf. Reaching 0 at an inner node, or at its empty child, does not count, because the path has not reached a leaf yet.
- As soon as one side returns true, the call returns true as well, so the rest of the tree is not visited.
Complexity
Time O(n): each node is visited at most once. Memory O(h), where h is the height of the tree: the call stack holds one path.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗