LeetCode: Nested List Weight Sum Posted on February 11, 2018July 26, 2020 by braindenny Nested List Weight Sum Similar Problems: Nested List Weight Sum II CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #nestedlist, #recursive, #dfs Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list — whose elements may also be integers or other lists. Example 1: Given the list [[1,1],2,[1,1]], return 10. (four 1's at depth 2, one 2 at depth 1) Example 2: Given the list [1,[4,[6]]], return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27) Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. ## https://code.dennyzhang.com/nested-list-weight-sum ## Basic Ideas: dfs ## ## Complexity: Time O(n), Space O(1) # """ # This is the interface that allows for creating nested lists. # You should not implement it, or speculate about its implementation # """ #class NestedInteger: # def __init__(self, value=None): # """ # If value is not specified, initializes an empty list. # Otherwise initializes a single integer equal to value. # """ # # def isInteger(self): # """ # @return True if this NestedInteger holds a single integer, rather than a nested list. # :rtype bool # """ # # def add(self, elem): # """ # Set this NestedInteger to hold a nested list and adds a nested integer elem to it. # :rtype void # """ # # def setInteger(self, value): # """ # Set this NestedInteger to hold a single integer equal to value. # :rtype void # """ # # def getInteger(self): # """ # @return the single integer that this NestedInteger holds, if it holds a single integer # Return None if this NestedInteger holds a nested list # :rtype int # """ # # def getList(self): # """ # @return the nested list that this NestedInteger holds, if it holds a nested list # Return None if this NestedInteger holds a single integer # :rtype List[NestedInteger] # """ class Solution: def depthSum(self, nestedList: List[NestedInteger]) -> int: def dfs(nums, level): if len(nums) == 0: return 0 res = 0 for v in nums: if v.isInteger(): res += v.getInteger() * level else: res += dfs(v.getList(), level+1) return res return dfs(nestedList, 1) Post Views: 5