Path Sum II

Intuition

Because a valid answer must be an entire root-to-leaf path, we can explore the tree depth-first and keep the list of values seen so far. Instead of recomputing sums, we subtract each node's value from the remaining target as we descend, so a match is simply the remaining target hitting zero at a leaf. The one subtlety is that the path list is shared across the whole traversal, so when we find a winning path we must store a copy rather than a reference. After visiting a node's children we pop that node from the path, restoring the state for the sibling branch. This push-explore-pop rhythm is classic backtracking and keeps the extra memory proportional to the tree height.

Algorithm walkthrough

1. 1Maintain a mutable path list and a results list; start the DFS from the root with remaining = targetSum.
2. 2On entering a node, append its value to path and subtract its value from remaining.
3. 3If the node is a leaf and remaining is now zero, push a copy of path into results.
4. 4Otherwise recurse into the left child and the right child with the updated remaining value.
5. 5Before returning, pop the current node's value from path so sibling branches see a clean state.
6. 6After the traversal completes, return the results list.

Implementation

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        result: List[List[int]] = []
        path: List[int] = []

        def dfs(node: Optional[TreeNode], remaining: int) -> None:
            if not node:
                return
            path.append(node.val)
            remaining -= node.val
            if not node.left and not node.right and remaining == 0:
                result.append(list(path))
            else:
                dfs(node.left, remaining)
                dfs(node.right, remaining)
            path.pop()

        dfs(root, targetSum)
        return result