Simple O(n) recursive python solution with explanation

  • 0

    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
                    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.