[leetcode/lintcode 題解] 算法面試真題：嵌套清單的權重和II

描述

給一個嵌套的整數清單, 傳回清單中所有整數由它們的深度權重後的總和. 每一個元素可能是一個整數或一個清單(其元素也可能是整數或清單)。

注意，在之前的題目嵌套清單的權重和中，從根結點到葉子結點，深度權重是遞增的。在嵌套清單的權重和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;
    }

}           

更多題解參考：

九章官網solution