Practice/Amazon/Leetcode 113. Path Sum II

Leetcode 113. Path Sum II

CodingMust

Problem

Given the root of a binary tree and an integer target sum, return all paths from the root to any leaf node where the sum of node values along the path equals the target sum. Each path should be represented as a list of node values in the order they appear from root to leaf.

A leaf node is defined as a node with no children. A path must start at the root and end at a leaf.

Requirements

1. Return all valid root-to-leaf paths as a list of lists, where each inner list contains node values
2. Each path must start at the root and end at a leaf node
3. The sum of values along each returned path must equal the target sum
4. Node values can be negative, zero, or positive
5. If no valid paths exist, return an empty list

Constraints

• The number of nodes in the tree is in the range [0, 5000]
• -1000 ≤ Node.val ≤ 1000
• -1000 ≤ targetSum ≤ 1000

Examples

Example 1:

` 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]] Explanation: The tree structure is: 5 /
4 8 / /
11 13 4 / \ /
7 2 5 1

Two paths sum to 22:

• 5 + 4 + 11 + 2 = 22
• 5 + 8 + 4 + 5 = 22 `

Example 2:

` Input: root = [1,2,3], targetSum = 5 Output: [] Explanation: The tree structure is: 1 /
2 3

Neither path sums to 5:

• 1 + 2 = 3
• 1 + 3 = 4 `

Example 3:

Input: root = [1,2], targetSum = 1 Output: [] Explanation: The only path is [1,2] which sums to 3, not 1. Note that [1] is not a valid path because node 1 is not a leaf.