Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values equals targetSum. Pattern focus: Root To Leaf Paths. Carry the current path and backtrack after exploring each branch.

Input Format

root = binary tree root, targetSum = required sum

Output Format

all root-to-leaf paths that sum to targetSum

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^4 <= node values <= 10^4
  • Input must satisfy the format described in inputFormat.

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:

There are two root-to-leaf paths with sum 22.

Example 2:

Input:

root = [1,2,3]
targetSum = 4

Output:

[[1,3]]

Explanation:

Only the path 1 -> 3 sums to 4.

Loading...
Path Sum II - Binary Tree DSA Problem