If the depth of a tree is smaller than 5, then this tree can be represented by an array of three-digit integers. You are given an ascending array nums consisting of three-digit integers representing a binary tree with a depth smaller than 5, where for each integer:
d of this node, where 1 <= d <= 4.p of this node within its level, where 1 <= p <= 8, corresponding to its position in a full binary tree.v of this node, where 0 <= v <= 9.Return the sum of all paths from the root towards the leaves.
It is guaranteed that the given array represents a valid connected binary tree.
Example 1:
Input: nums = [113,215,221]
Output: 12
Explanation:
The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.
Example 2:
Input: nums = [113,221]
Output: 4
Explanation:
The tree that the list represents is shown.
The path sum is (3 + 1) = 4.
Constraints:
1 <= nums.length <= 15110 <= nums[i] <= 489nums represents a valid binary tree with depth less than 5.nums is sorted in ascending order.Problem Overview: The input represents a binary tree using three-digit integers where the hundreds digit is the depth, the tens digit is the position within that level, and the units digit is the node value. Your task is to reconstruct the structure logically and compute the total of all root‑to‑leaf path sums.
Approach 1: Build the Binary Tree then DFS (O(n) time, O(n) space)
A straightforward method is to explicitly build the tree structure first. Parse each number to extract depth, position, and value, then map each node to its parent using the rule that a node at (d, p) has a parent at (d-1, (p+1)//2). Once the structure is built, run a standard Depth-First Search from the root, accumulating path sums until reaching leaf nodes. Each leaf contributes its path total to the final answer. This approach mirrors how you normally solve path sum problems on a Binary Tree, making it easy to reason about during implementation.
Approach 2: Hash Map + Implicit DFS (O(n) time, O(n) space)
A more efficient approach avoids building the full tree. Store each node in a Hash Table using a key like depth * 10 + position. Then run DFS starting from the root (depth 1, position 1). For each node, compute the keys of its potential children: left child at (d+1, 2p-1) and right child at (d+1, 2p). If neither child exists in the map, the node is a leaf and the current path sum gets added to the result. Otherwise, continue DFS with the updated sum. This method leverages the encoded structure directly and avoids explicit node objects.
The key insight is that the position encoding uniquely determines parent‑child relationships. Because each node can be found with a constant‑time hash lookup, the traversal runs in linear time relative to the number of encoded nodes.
Recommended for interviews: The hash map + implicit DFS approach. It demonstrates that you understand how the positional encoding works and can reconstruct relationships without building a full tree. Mentioning the explicit tree construction approach first can show baseline understanding, but the optimized DFS with hash lookups shows stronger problem‑solving ability.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Build Tree then DFS | O(n) | O(n) | When you want a clear tree structure and standard DFS traversal |
| Hash Map + Implicit DFS | O(n) | O(n) | General case; avoids building the tree and uses constant-time lookups |
贾考博 LeetCode 666. Path Sum IV • 贾考博 • 1,126 views views
Watch 5 more video solutions →Practice Path Sum IV with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor