LeetCode #113 Medium

Path Sum II

Given the root of a binary tree and a target sum, return every root-to-leaf path whose values add up to the target.

binary treedfsbacktracking

02

Intuition

💡

The trap is appending the live path list straight into your results. Lists in most languages are passed by reference, so if you push the same list object into the answer at every matching leaf, every entry ends up pointing at the exact same array -- and once you pop values off it on the way back up (which you must, to backtrack correctly), all your saved results silently turn into the same, usually empty, list. The fix is to append a copy of the path at the moment of the match, not the list itself. Keep one shared path list for the whole DFS, push a value going down, check the leaf condition, save a copy if it hits, then pop the value going back up regardless of whether it matched. That push-then-pop symmetry is the invariant: the path list must be exactly restored to its parent's state by the time you return to the parent.

03

Approach

1

Track a running path and remaining target

Do a DFS that carries two pieces of state: the list of values from the root down to the current node, and the remaining amount needed to hit the target. At each node, append the node's value to the path and subtract it from the remaining sum before recursing into children.

2

On a leaf, copy before you save

When both children are null, check whether remaining has hit exactly zero. If it has, this path is a valid answer -- but append path[:] (or list(path)), not path itself, because path keeps being mutated as the recursion continues to explore other branches.

3

Pop on every return, matched or not

After recursing into both children (or after handling a leaf), pop the last value off the path before returning to the caller. This undoes the push from this call and restores the path to exactly what the parent expects, whether or not this subtree produced a match.

04

Solution & live demo

python

▶1class Solution:
▶2    def pathSum(self, root, targetSum):
▶3        res = []
▶4        path = []
▶5        def dfs(node, remaining):
▶6            if not node:
▶7                return
▶8            path.append(node.val)
▶9            remaining -= node.val
▶10            if not node.left and not node.right:
▶11                if remaining == 0:
▶12                    res.append(path[:])
▶13            else:
▶14                dfs(node.left, remaining)
▶15                dfs(node.right, remaining)
▶16            path.pop()
▶17        dfs(root, targetSum)
▶18        return res

05

Edge cases

Empty tree

Return an empty list immediately; there are no root-to-leaf paths.

Target sum of 0 with negative values on the path

The running sum can dip below zero and climb back to exactly zero at a leaf; only equality at a leaf counts, so keep summing all the way down rather than pruning early on a negative partial sum.

Single node whose value equals the target

The root is also a leaf; the path [root.val] should be recorded as one of the results.

Multiple valid paths sharing a prefix

Because each result is a copy taken at its own leaf, two paths that share ancestors do not interfere with each other in the output even though they briefly shared the same path list in memory.

06

Complexity

Time

O(n^2)

Space

O(n)

Each of n nodes is visited once, but copying the path at a match can cost O(n); recursion depth (and the path list) is O(h), worst case O(n) on a skewed tree.