668. Path Sum IV
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:
- The hundreds digit represents the depth d of this node, where 1 <= d <= 4.
- The tens digit represents the position p of this node within its level, where 1 <= p <= 8, corresponding to its position in a full binary tree.
- The units digit represents the value 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: [113, 215, 221]
Output: 12
Explanation:
The input array represents a binary tree where each number is a three-digit integer. The hundreds digit indicates the node's depth (from 1 to 4), the tens digit shows its position in that level (following the structure of a full binary tree), and the units digit is the node's value. For this example, 113 corresponds to a node at depth 1, position 1 with a value of 3 (the root). The number 215 represents a node at depth 2, position 1 with a value of 5, and 221 represents a node at depth 2, position 2 with a value of 1. This builds the tree as follows: the root node 3 has two children—5 on the left and 1 on the right. The sum of the left path is 3 + 5 = 8 and the right path is 3 + 1 = 4, giving a total sum of 8 + 4 = 12.
Example 2:
Input: [113, 221]
Output: 4
Explanation:
In this example, 113 is the root node at depth 1, position 1 with a value of 3, and 221 is a node at depth 2, position 2 with a value of 1. This forms a tree where the root node 3 only has a right child 1. Hence, the only root-to-leaf path is 3 → 1, which sums up to 3 + 1 = 4.
Now Your Turn!
Pick the correct output for the given inputInput: [118,210,229,341,472,483 ]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= nums.length <= 15
- 110 <= nums[i] <= 489
- nums represents a valid binary tree with depth less than 5.
- nums is sorted in ascending order.