嵌套列表的加权和II

https://www.lintcode.com/problem/905/description?utm_source=sc-libao-ql

描述

给一个嵌套的整数列表, 返回列表中所有整数由它们的深度加权后的总和. 每一个元素可能是一个整数或一个列表(其元素也可能是整数或列表)。 注意，在之前的题目嵌套列表的加权和中，从根结点到叶子结点，深度权重是递增的。在嵌套列表的加权和II中，深度权重的定义是自下而上的，也就是说，最底层叶子结点的深度权重是1 ，根结点的深度权重最大。

样例

样例 1:

输入: nestedList = [[1,1],2,[1,1]]输出: 8解释：四个深度为 1 的 1，一个深度为 2 的 2

样例 2:

输入: nestedList = [1,[4,[6]]]输出: 17解释：一个深度为 3 的 1， 一个深度为 2 的 4，和一个深度为 1 的 61*3 + 4*2 + 6*1 = 17

解题分析：

用bfs遍历，得到层数和每一层的总和，存入一个map。最后sum map里的总和，注意根部的层数最大，需要特殊处理。

错误点：每层需要计算level sum, 而不是直接单独每个Int 加入map，因为int 有重复，直接存入Map被覆盖。

from collections import deque
class Solution:
    """
    @param nestedList: a list of NestedInteger
    @return: the sum
    """
   
    def depthSumInverse(self, nestedList):
        # Write your code here.
        q = deque(nestedList)
        level = 0
        items = {}

        while q:
            level += 1
            n = len(q)
            levelsum = 0
            for _ in range(n):
                cur = q.popleft()
                if cur.isInteger():
                    levelsum += cur.getInteger()                 
                else:                   
                    q.extend(cur.getList())
            items[levelsum] = level
                    
        return sum(k*(abs(level-v)+1) for k,v in items.items())