Path sum iv

class Solution:
    def __init__(self):
        self.ans = 0
    def solve(self, d, depth, pos, res):
        left = pos * 2 - 1
        right = pos * 2
        if depth + 1 not in d:
            self.ans += res + d[depth][pos]
            return 
        if left not in d[depth + 1] and right not in d[depth + 1]:
            self.ans += res + d[depth][pos]
            return 
        if left in d[depth + 1]:
            self.solve(d, depth + 1, left, res + d[depth][pos])
        if right in d[depth + 1]:
            self.solve(d, depth + 1, right, res + d[depth][pos])

    def pathSum(self, nums: List[int]) -> int:
        tree = {}
        for i in range(len(nums)):
            node = str(nums[i])
            level = int(node[0])
            pos = int(node[1])
            val = int(node[2])
            if level not in tree:
                tree[level] = {}
            tree[level][pos] = val

        self.solve(tree, 1, 1, 0)

        return self.ans

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. For each integer in this array:

• The hundreds digit represents the depth d of this node where 1 <= d <= 4.
• The tens digit represents the position p of this node in the level it belongs to where 1 <= p <= 8. The position is the same as that in a full binary tree.
• The units digit represents the value v of this node where 0 <= v <= 9.

Given an array of ascending three-digit integers nums representing a binary tree with a depth smaller than 5, 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 <= 15
• 110 <= nums[i] <= 489
• nums represents a valid binary tree with depth less than 5.