Path Sum II
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]]
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;}