DFS O(n) solution, with detailed explanation


  • 0
    C

    So the idea is very similar to Nested List Weight Sum I except that in this case every successive dfs call reduces level by 1.
    Now if you're asking how do we know the level in the first place. Well simple, compute it in advance using a similar recursive approach.
    Separating the problem into two separtae tasks just makes it more readable and understandable.

        def depthSumInverse(self, nestedList):
            """
            :type nestedList: List[NestedInteger]
            :rtype: int
            """
            depth = self.compute_depth(nestedList)
            return self.depth_sum_inverse_helper(nestedList, depth)
    
        def depth_sum_inverse_helper(self, nestedList, depth):
            total = 0
            for item in nestedList:
                if item.isInteger():
                    total += item.getInteger() * depth
                else:
                    total += self.depth_sum_inverse_helper(item.getList(), depth-1)
            return total
    
        # This method computes the depth of the tree in advance.
        def compute_depth(self, nestedList):
            depth = 1
            for item in nestedList:
                if not item.isInteger():
                    depth = max(depth, self.compute_depth(item.getList()) + 1)
            return depth
    

Log in to reply
 

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