Finding All Root-to-Leaf Paths with a Target Sum

Imagine you have a binary tree representing a hierarchical structure. We're interested in finding all the paths from the root of this tree down to any leaf node where the sum of the node values along that path equals a specific target sum. This is a fundamental problem in tree traversal and has applications in areas like data analysis and game development where specific path properties are important.

Problem Description

Given the root of a binary tree and an integer targetSum, find all root-to-leaf paths where the sum of the values along the path equals targetSum.

A root-to-leaf path is a sequence of nodes starting from the root and ending at any leaf node. A leaf node is a node with no children.

You should return a list of lists, where each inner list represents a valid root-to-leaf path that sums up to targetSum. The order of the paths in the output list does not matter. The order of nodes within each path should follow the path from root to leaf.

Key Requirements:

• Identify all paths from the root to a leaf node.
• Calculate the sum of node values for each path.
• Return only those paths whose sum equals targetSum.

Edge Cases to Consider:

• An empty tree (root is null).
• A tree with only a root node.
• Paths that sum to targetSum but do not end at a leaf. These should be excluded.
• Paths that end at a leaf but do not sum to targetSum. These should also be excluded.

Examples

Example 1:

Input:
    root = [5,4,8,11,null,13,4,7,2,null,null,5,1]
    targetSum = 22

Visual Representation:
        5
       / \
      4   8
     /   / \
    11  13  4
   /  \    / \
  7    2  5   1

Output: [[5,4,11,2],[5,8,4,5]]

Explanation:
The paths that sum to 22 are:
- 5 -> 4 -> 11 -> 2 (sum = 5 + 4 + 11 + 2 = 22)
- 5 -> 8 -> 4 -> 5 (sum = 5 + 8 + 4 + 5 = 22)
The path 5 -> 8 -> 4 -> 1 (sum = 5 + 8 + 4 + 1 = 18) is not included.
The path 5 -> 4 -> 11 -> 7 (sum = 5 + 4 + 11 + 7 = 27) is not included.

Example 2:

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

Visual Representation:
        1
       / \
      2   3

Output: []

Explanation:
The only root-to-leaf paths are:
- 1 -> 2 (sum = 3)
- 1 -> 3 (sum = 4)
Neither path sums to 5.

Example 3:

Input:
    root = [1,2]
    targetSum = 0

Visual Representation:
        1
       /
      2

Output: []

Explanation:
The only root-to-leaf path is 1 -> 2, with a sum of 3.

Constraints

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000
• The tree structure is a valid binary tree.

Notes

• You will need to traverse the tree. Consider recursive or iterative approaches.
• Keeping track of the current path and its sum as you traverse will be crucial.
• When you reach a leaf node, check if the current path's sum matches the targetSum. If it does, add a copy of the current path to your results.
• Remember to backtrack or manage your path data structure correctly when returning from recursive calls or processing siblings in an iterative approach.