deepSWE.io

Path Sum II

TreesDFS

25 min

Problem Statement

Given the root of a binary tree and an integer `targetSum`, return all root-to-leaf paths where the sum of the node values in the path equals `targetSum`. Each path should be returned as a list of the node values, not node references.

Example

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]]

Solution: Depth-First Search (DFS)

The problem can be solved efficiently using a recursive Depth-First Search. We traverse the tree, keeping track of the current path and the remaining sum.

Algorithm Steps

Create a recursive function `dfs(node, remainingSum, path, result)`.
Base Case: If `node` is null, return.
Add the current node to the `path`.
If the current node is a leaf and its value equals the `remainingSum`, add the current `path` to the `result`.
Recursively call `dfs` on the left and right children.
Backtrack by removing the current node from the `path`.

Paths Found: 0

Visiting node 5. Remaining sum: 17.

Path Sum II Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        
        def dfs(node, remaining_sum, path):
            if not node:
                return
            
            path.append(node.val)
            
            if not node.left and not node.right and remaining_sum == node.val:
                res.append(list(path))
            
            dfs(node.left, remaining_sum - node.val, path)
            dfs(node.right, remaining_sum - node.val, path)
            
            path.pop()

        dfs(root, targetSum, [])
        return res