描述

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

在线评测地址

样例 1:

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

样例 2:

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

主要思路：

bfs 遍历列表每一层，如果是数字，则加到当前这一层的和当中，反之，是列表，则进入队列，每一层遍历完，才进入下一层，最后将每一层的数值加到结果当中即可。

public class Solution {     /**      * @param nestedList: a list of NestedInteger      * @return: the sum      */     public int depthSumInverse(List<NestedInteger> nestedList) {          // corner case          if(nestedList == null || nestedList.size() == 0) {              return 0;          }           // initialize          int preSum = 0;          int result = 0;          // put each item of list into the queue          Queue<NestedInteger> queue = new LinkedList<>(nestedList);          while(!queue.isEmpty()){              //depends on different depth, queue size is changeable              int size = queue.size();              int levelSum = 0;              for(int i = 0; i < size; i++){                  NestedInteger n = queue.poll();                  if(n.isInteger()){                      levelSum += n.getInteger();                  }                  else{                      // depends on different depth, queue size is changeable                      queue.addAll(n.getList());                  }              }              preSum += levelSum;              result += preSum;          }          return result;     }  } 

更多题解参考

大佬有話說 (0)