Store each level using hash table DFS [Accepted]

  • 0
    • Traverse whole nestedLists (DFS), store all integers into a dictionary base on their weights.
    • Using 0 to -n (0<n) to represent weights(levels).
    • Using formula (level + maxLevel) * sum(Integer List for level m]), maxLevel is (absolute value of the lastest level) + 1
    class Solution(object):
        def depthSumInverse(self, nestedList):
            global maxLevel
            maxLevel = 0
            dic = {}
            def helper(nestedList, level):
                global maxLevel
                for l in nestedList:
                    # record the lastest level
                    maxLevel = min(level, maxLevel)                 
                    if l.isInteger():
                        if level in dic:
                            dic[level] = [l.getInteger()]
                        # read nestedList from next level
                        helper(l.getList(), level-1)                
            helper(nestedList, 0)  
            weightedSUM = 0
            # each level in dic should be updated by adding this
            maxLevel = abs(maxLevel) + 1                            
            for level in dic:
                # calculate the weighted sum for all levels
                weightedSUM += (level + maxLevel) * sum(dic[level])     
            return weightedSUM

Log in to reply

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