We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Path Sum II

Difficulty: Medium

Problem Description

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.

Key Insights

  • A root-to-leaf path is defined as a path starting from the root and ending at a leaf node.
  • A leaf node is a node that does not have any children.
  • The problem requires a backtracking approach to explore all possible paths from the root to the leaves.
  • The sum of the node values along the path must be checked against the targetSum.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the binary tree, since we may visit every node once.
Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.

Solution

To solve the problem, we can use a depth-first search (DFS) strategy combined with backtracking. We will traverse the tree starting from the root, keeping track of the current path and the remaining sum required to reach the targetSum. When we reach a leaf node, we check if the remaining sum is zero, indicating that we have found a valid path. If so, we add that path to our results. If not, we backtrack and continue exploring other paths.

Code Solutions

def pathSum(root, targetSum):
    def dfs(node, currentPath, currentSum):
        if not node:
            return
        currentPath.append(node.val)
        currentSum += node.val
        # Check if it's a leaf node and if the current sum equals the target sum
        if not node.left and not node.right and currentSum == targetSum:
            result.append(list(currentPath))
        # Recur for left and right children
        dfs(node.left, currentPath, currentSum)
        dfs(node.right, currentPath, currentSum)
        # Backtrack
        currentPath.pop()
        
    result = []
    dfs(root, [], 0)
    return result
← Back to All Questions