---
link: https://leetcode.com/problems/path-sum-iv/
tags: array, tree, bt
---

# 666. Path Sum IV

## Question
If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.

For each integer in this list:

1.The hundreds digit represents the depth D of this node, 1 <= D <= 4.
2.The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
3.The units digit represents the value V of this node, 0 <= V <= 9.

Given a list of ascending three-digits integers representing a binary tree with the depth smaller than 5, you need to return the sum of all paths from the root towards the leaves.

Example 1:

Input: [113, 215, 221]
Output: 12
Explanation: 
The tree that the list represents is:
    3
   / \
  5   1

The path sum is (3 + 5) + (3 + 1) = 12.

Example 2:

Input: [113, 221]
Output: 4
Explanation: 
The tree that the list represents is: 
    3
     \
      1

The path sum is (3 + 1) = 4.

## Solution: Python

class Solution:
    """
    @param nums: the list
    @return: the sum of all paths from the root towards the leaves
    """
    def pathSumIV(self, nums):
        nums.sort()
        self.path_sums = 0
        self.els = {num / 10: num for num in nums}
        
        if nums is None:
            return self.path_sums
        
        self.getPathSum(nums[0], 0)
        return self.path_sums
    
    def getPathSum(self, el, path_total):
        if el is None:
            return
        
        node = self.getNode(el)
        path_total += node.val

        if node.left is None and node.right is None:
            self.path_sums += path_total
            return
            
        self.getPathSum(node.left, path_total)
        self.getPathSum(node.right, path_total)
    
    def getNode(self, el):
        level = el / 100 % 10
        position = el / 10 % 10
        value = el % 10
        
        children_level = level + 1
        position_level_left = 2 * (position - 1) + 1
        position_level_right = 2 * (position - 1) + 2
        
        node = TreeNode(value)
        node.left = self.els.get(children_level * 10 + position_level_left)
        node.right = self.els.get(children_level * 10 + position_level_right)
        
        return node

## Solution: Java