147. Path Sum II

Medium · Binary Tree

Given a binary tree and a target sum, find all root-to-leaf paths where the sum of node values equals the target sum.

Input: An array `[arr, targetSum]` where `arr` is a level-order serialization of a binary tree (with `null` for missing nodes) and `targetSum` is an integer. A leaf node is one with no children.

Output: Return a list of all root-to-leaf paths that sum to `targetSum`. Each path is a list of node values from root to leaf. The outer list must be sorted lexicographically (using JSON.stringify comparison) so the grader can verify your answer.

Examples

Example 1
Input: [[5,4,8,11,null,13,4,7,2,null,null,5,1], 22]
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: Two root-to-leaf paths sum to 22
Example 2
Input: [[1,2,3], 5]
Output: []
Explanation: No matching root-to-leaf paths

Constraints