LeetCode Solutions Blog

Path Sum IV

Number: 666

Difficulty: Medium

Paid? Yes

Problem Description

Given an ascending array of three-digit integers where each integer represents a node in a binary tree, decode the tree structure and return the sum of all the path sums from the root to each leaf. The hundreds digit represents the depth (1 <= d <= 4), the tens digit represents the position within the level (following the full binary tree indexing), and the units digit represents the node's value.

Key Insights

The encoded integer has three parts: depth, position, and value.
The tree is represented implicitly; using the depth and position, compute the keys for left and right children.
Use a dictionary (or map) to store nodes for constant time lookup.
Use depth-first search (DFS) to traverse from the root to each leaf, maintaining a running sum.
When a leaf node is reached, add its path sum to the total result.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes (at most 15), since each node is visited once. Space Complexity: O(N) for the recursion stack and node map storage.

Solution

We convert each three-digit number into a key formed by depth * 10 + position and store its value in a dictionary. The left child of a node at (d, p) is at (d+1, 2p-1) and the right child is at (d+1, 2p). Using DFS, we start at the root (key 11) and traverse the tree, accumulating the path sum until we reach a leaf (a node without any children). The sum of all root-to-leaf path sums is then computed.

Code Solutions

def pathSum(nums):
    # Create a dictionary to store nodes: key = depth * 10 + position, value = node value
    node_map = {}
    for num in nums:
        depth = num // 100                     # Extract the node depth
        position = (num % 100) // 10           # Extract the node position
        value = num % 10                       # Extract the node value
        key = depth * 10 + position            # Create a unique key for this node
        node_map[key] = value

    # Define a recursive DFS function to explore path sums from the current node
    def dfs(key, current_sum):
        if key not in node_map:
            return 0  # If the node does not exist, return 0
        current_sum += node_map[key]  # Update the path sum with the current node's value
        depth = key // 10            # Obtain node's depth from key
        position = key % 10          # Obtain node's position from key
        # Calculate keys for left and right children
        left_key = (depth + 1) * 10 + (2 * position - 1)
        right_key = (depth + 1) * 10 + (2 * position)
        # If both children do not exist, it's a leaf node, so return the path sum
        if left_key not in node_map and right_key not in node_map:
            return current_sum
        # Continue DFS on left and right children and return the combined sums
        return dfs(left_key, current_sum) + dfs(right_key, current_sum)

    # Start DFS from the root node (key = 11) with an initial sum of 0
    return dfs(11, 0)

# Example usage:
print(pathSum([113, 215, 221]))  # Expected output: 12