[LeetCode] 666. Path Sum IV

 Problem : https://leetcode.com/problems/path-sum-iv/

Reconstruct the tree and them use DFS to get the path sums.

Because index starts from 1, for node coordinate (y, x):

-  left child coordinate on next level =  (y + 1,  2 * x - 1)

- right child coordinate on next level = (y + 1,  2 * x)

class Solution:
    def pathSum(self, nums: List[int]) -> int:
        
        tree = {}
        
        for n in nums:
            y = n // 100
            n = n % 100
            x = n // 10
            n = n % 10
            tree[(y, x)] = n
            
        
        def dfs(y, x, sums):
            if (y, x) in tree:
                sums += tree[(y,x)]
                
                # since index starts from 1
                # left child coordination = (y+1, 2*x - 1)
                # right child coordination = (y+1, 2*x)
                if (y+1, 2*x - 1) not in tree and (y+1, 2*x) not in tree:
                    yield sums
                else:
                    yield from dfs(y+1, 2*x-1, sums)
                    yield from dfs(y+1, 2*x, sums)
        
        
        return sum(dfs(1, 1, 0))