Simple O(n) recursive python solution with explanation


  • 0
    C

    This approach really isn't new and many have used it before. The idea is the NestedInteger is a recursive data structure thus DFS is the natural approach.
    The algorithm is pretty straightforward.
    Iterate the list if it's an integer, add the value, if not recurse with 1 added to the level.

        def depthSum(self, nestedList):
            """
            :type nestedList: List[NestedInteger]
            :rtype: int
            """
            return self.helper(nestedList, 1)
    
        def helper(self, nestedList, level):
            total = 0
            for item in nestedList:
                if item.isInteger():
                    total += item.getInteger() * level
                else:
                    total += self.helper(item.getList(), level + 1)
            return total
    

Log in to reply
 

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