Path Sum II
Medium · Trees · Tree · Depth-First Search · Backtracking · Binary Tree
Problem
Given the root of a binary tree and an integer targetSum, return every root-to-leaf path whose node values add up to targetSum.
Return each path as a list of node values, from the root down to the leaf. A leaf is a node with no children. The paths may be listed in any order.
Examples
Input: root = [4,2,6,3,1,5,-1], targetSum = 9 Output: [[4,2,3],[4,6,-1]]
Two root-to-leaf paths add up to 9: 4 + 2 + 3 and 4 + 6 + (-1). The other two sum to 7 and 15.
Input: root = [1,2], targetSum = 1 Output: []
The only leaf is 2, and the path 1 -> 2 sums to 3. The root alone is not a path because it has a child.
Input: root = [], targetSum = 0 Output: []
An empty tree has no root-to-leaf paths.
Constraints
- The number of nodes is in the range [0, 5000]
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
Approaches
- List every path, then filter — time O(n · h), space O(n · h)
Follow-up
If paths may start and end at any node going downward, keep a map of prefix sums along the current root path: a path ending here sums to the target when prefix - target was seen above. That counts them in O(n) instead of O(n · h).
Related problems
Start free on Cariara · Coding problems · System design studio
