Path Sum II

Construct Binary Tree from Preorder & Inorder

Merge Two Binary Trees

Return every root-to-leaf path in a binary tree whose values sum to a given target.

Given the `root` of a binary tree and an integer `targetSum`, return **all** root-to-leaf paths where each path's node values sum to `targetSum`.

A leaf is a node with no children. Each returned path should list node values from root to leaf, in order.

**Input / output**
- Input: `root: TreeNode`, `targetSum: int` (JSON test fixture for `root` is a LeetCode-style level-order array, e.g. `[5,4,8,11,null,13,4,7,2,null,null,5,1]`, with `null` for a missing child)
- Output: `int[][]`, one row per matching path, each row root-to-leaf in order (rows may appear in any order that matches a valid DFS traversal order)

## Example
```json
Input: {"root":[5,4,8,11,null,13,4,7,2,null,null,5,1],"targetSum":22}
Output: [[5,4,11,2],[5,8,4,5]]
```

## Constraints
- 0 <= number of nodes <= 5,000
- -1,000 <= node value <= 1,000
- -1,000 <= targetSum <= 1,000

## Follow-up
How would you adapt this to return the paths as soon as a match is found, without holding the full result set in memory at once?

The key pattern is: DFS with backtracking — push the current node onto a shared path buffer, recurse, then pop it back off after both children have been explored, so every leaf sees the exact path that led to it.

Recognize the Pattern

Advance one state transition at a time. Mark or update state before exploring dependent work.

Build the Algorithm

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

Check Edge Cases

Time: O(n^2) worst case — every node is visited once (O(n)), and each of up to O(n) valid paths can be up to O(n) long to copy into the result. Space: O(n) for the recursion stack and the current path buffer, not counting the output.

All 5 languages below run and submit against the remote judge for this problem — Java/Go/Rust use the same real TreeNode structural-type support the judge added for the rest of the linked-list/tree track.