Given the root of a binary tree and an integer target, return all root-to-leaf paths whose values add up to target. Each path is a list of node values from the root down to the leaf. Paths may be returned in any order. Return [] if no path qualifies.
Examples
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Input: root = build_tree([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, 5, 1]), target = 22
Output: [[5, 4, 11, 2], [5, 8, 4, 5]]
Input: root = build_tree([1, 2, 3]), target = 5
Output: []
Constraints
0 <= number of nodes <= 1000-1000 <= node.val, target <= 1000
Goals
- Track the remaining sum while descending
- Copy a path when it is recorded so later backtracking does not change it