Problem statement

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

Solution

A bit strange in my opinion, but not difficult problem: let us create empty full binary tree with 5 levels, then first fill nodes, traversing nums. Then use simple dfs to find sum of all paths.

Complexity

Time complexity of all algorithm is O(32), because this is number of nodes in our tree.

Code

class Solution:
    def pathSumIV(self, nums):
        tree = [[-1],[-1]*2,[-1]*4,[-1]*8, [-1]*16]
        for num in nums:
            dep, pos, val = [int(i) for i in list(str(num))]
            tree[dep-1][pos-1] = val
            
        def dfs(d,w,s):
            if tree[d+1][2*w] == -1 and tree[d+1][2*w+1] == -1:
                self.res += s
            
            for child in [2*w, 2*w+1]:
                if tree[d+1][child] != -1:
                    dfs(d+1, child, s+tree[d+1][child])
                
        self.res = 0
        dfs(0,0,tree[0][0])
        return self.res