LeetCode 364 Nested List Weight Sum II

LeetCode

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer’s value set to its depth. Let maxDepth be the maximum depth of any integer.

The weight of an integer is maxDepth - (the depth of the integer) + 1.

Return the sum of each integer in nestedList multiplied by its weight.

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1’s with a weight of 1, one 2 with a weight of 2.
11 + 11 + 22 + 11 + 11 = 8

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: 17
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1.
13 + 42 + 61 = 17

Constraints:

1 <= nestedList.length <= 50 The values of the integers in the nested list is in the range [-100, 100].
The maximum *depth of any integer is less than or equal to 50.

题目大意：

求NestedInteger的和。越浅，权重越高

解题思路：

BFS按层遍历。此题类似于LeetCode 339 Nested List Weight Sum。归纳成更一般的方法：因为权重只与第几层有关。所以先求每一层的和，存到sums里面，再按照题目要求每个和乘以相应的权重求和。

Nested List题目：
LeetCode 341 Flatten Nested List Iterator Iterator - Stack
LeetCode 339 Nested List Weight Sum - BFS
LeetCode 364 Nested List Weight Sum II - BFS

解题步骤：

N/A

注意事项：

1. queue.extend(node.getList())将节点的儿子节点即node.getList()放入queue

Python代码：

def depthSumInverse(self, nestedList) -> int:
	queue = collections.deque(nestedList)
	sums, max_depth, res = [], 0, 0
	while queue:
		layer_sum = 0
		for _ in range(len(queue)):
			node = queue.popleft()
			if node.isInteger():
				layer_sum += node.getInteger()
			else:
				queue.extend(node.getList()) # remember
		sums.append(layer_sum)
		max_depth += 1
	for i, n in enumerate(sums):
		res += n * (max_depth - i)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(k), k为每层最多节点数 + 最大层数