All problems

Path Sum II

Medium · tree dfs

You are given the root of a binary tree and an integer target_sum. Find every root-to-leaf path whose node values add up to exactly target_sum, and return them as a list of paths.

A leaf is a node with no children at all. A path always starts at the root and ends at a leaf, so a node that has one child is not a leaf. Each path is a list of the values on it, from the root down.

List the paths in the order their leaves appear from left to right in the tree. If no path matches, or the tree is empty, return an empty list.

Examples

Example 1

Input: root = [6, 4, 7, 2, 5, 3, 1, 3, null, 1, 2], target_sum = 16

Output: [[6, 4, 5, 1], [6, 7, 3]]

Two paths add up to 16. The one ending in the leaf 1 under 5 is further left than the one ending in the leaf 3 under 7, so it comes first.

Example 2

Input: root = [6, 4, 7, 2, 5, 3, 1, 3, null, 1, 2], target_sum = 15

Output: [[6, 4, 2, 3]]

Example 3

Input: root = [1, 2, 3], target_sum = 5

Output: []

The paths are 1 + 2 = 3 and 1 + 3 = 4, so none match.

Constraints

• The number of nodes is in the range [0, 1000].
• -1000 <= Node.val <= 1000
• -10^6 <= target_sum <= 10^6
• At most 100 root-to-leaf paths add up to target_sum.