Path Sum II

Medium

Problem

Return every root-to-leaf path whose node values sum to targetSum, each as a list of values.

Example 1

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

Test cases

Case 1

Input:    [5,4,8,11,null,13,4,7,2,null,null,5,1], 22
Expected (any order): [[5,4,11,2],[5,8,4,5]]

Case 2

Input:    [1,2,3], 5
Expected (any order): []

Case 3

Input:    [1], 1
Expected (any order): [[1]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. DFS with a path (backtracking)

Time O(n²) worst case — copying pathsSpace O(h)

Push the node, subtract its value; at a leaf with remaining 0 record a copy; pop on the way back.

function pathSum(root, target) {
const res = [], path = [];
const dfs = (node, rem) => {
if (!node) return;
path.push(node.val);
rem -= node.val;
if (!node.left && !node.right && rem === 0) res.push([...path]);
dfs(node.left, rem);
dfs(node.right, rem);
path.pop();
};
dfs(root, target);
return res;
}