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:

Input: [[1,1],2,[1,1]]Output: 10 Explanation: Four 1's at depth 2, one 2 at depth 1.

Example 2:

Input: [1,[4,[6]]]Output: 27 Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27.

题意：

嵌套列表加权和

 

Solution1： BFS(level order traversal) 是最快的

 

code

1 class Solution { 2    public int depthSum(List
     
       nestedList) { 3        // corner case  4         if(nestedList == null){
   return 0;}  5        // initialize 6         int result = 0; 7         int depth = 1; 8        // put each item of list into the queue 9         Queue
      
        queue = new LinkedList<>(nestedList);10         while(!queue.isEmpty()){11             // depends on different depth, queue size is changeable 12             int size = queue.size();  13             for(int i = 0; i < size; i++){14                 NestedInteger n = queue.poll();15                 if(n.isInteger()){16                     result += n.getInteger() * depth;17                 }else{18                     // put each item of list into the queue19                     queue.addAll(n.getList());20                 }21             }22             depth++;23         } 24     return result;25     }26 }
      
     

注意：   put each item of list into the queue 的写法有：

Queue
     
       queue = new LinkedList<>(nestedList);
     

 

for（NestedInteger n :nestedList）{　　　　queue.add(n)}

queue.addAll(nestedList)

 

Solution2: DFS

code

1 class Solution { 2     public int depthSum(List
     
       nestedList) { 3         if(nestedList == null) return 0; 4         return dfs(nestedList, 1);     5     } 6      7     private int dfs(List
      
        nestedList, int depth){ 8         int result = 0; 9         for(NestedInteger n : nestedList ){10             if(n.isInteger()){11                 result = result + n.getInteger()*depth;12             }else{13                 result = result + dfs(n.getList() , depth+1);14             }  15         }16         return result ;17     }18 }