Python Non Recursive solution using dictionary, easy to understand self documented code


  • 0
    A

    Use a dictionary to store the sum of path up to and including the element value. Any subsequent child can then add its own value to its parent value and put it in the dict. And if this element is a leaf (checked from the dictionary) then we can add its value to the resulting sum. Dictionary keys are chosen to be of the form num[i]/10 because they are guaranteed to be unique for the tree.

    class Solution(object):
        def pathSum(self, nums):
            summ=0
            a = {x/10: 0 for x in nums}  #dictionary
            
            for i in xrange(len(nums)):
                height,pos,value = nums[i]/100, (nums[i]/10)%10, nums[i]%10
                parent = (height-1)*10 + (pos+1)/2
                value += a.get(parent,0)
                
                leftchild = (height+1)*10 + (2*pos-1)
                rightchild = leftchild + 1
                if leftchild not in a and rightchild not in a:
                    summ+=value
                else:
                    a[nums[i]/10]=value
            
            return summ
    

Log in to reply
 

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