Python - using dictionary and computing parent index


  • 0
    S
    class Solution(object):
        def pathSum(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            parent = dict()
            last   = -1
            
            parent[1] = [nums[0]%10,False]   # [path sum, not-leaf]
            
            for i in range(1,len(nums)):
                num    = nums[i]
                level, index, value = num//100 - 1, num%100//10, num%10
                array_index = 2**level - 1 + index
                parent_index = array_index // 2
                parent[array_index] = [ value + parent[parent_index][0], False]
                parent[parent_index][1] = True
                
            result = 0
            for key in parent.keys():
                if parent[key][1] == False:
                    result += parent[key][0]
            
            return result
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.