Medium

Quiz

#113 Path Sum II

APPROACH

Given the root of a binary tree and an integer targetSum, find every root-to-leaf path whose node values sum to targetSum. Return each path as a list of node values (not node references).

A root-to-leaf path starts at the root and ends at a leaf. A leaf is a node with no children.

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 paths whose sum equals targetSum:

5 + 4 + 11 + 2 = 22

5 + 8 + 4 + 5 = 22

Example 2:

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

Output: []

Example 3:

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

Output: []

1 of 4

1:00

What is the optimal approach for this problem?