Nested List Weight Sum

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.

这道题定义了一种嵌套链表的结构，链表可以无限往里嵌套，规定每嵌套一层，深度加1，让我们求权重之和，就是每个数字乘以其权重，再求总和。那么我们考虑，由于嵌套层数可以很大，所以我们用深度优先搜索DFS会很简单，每次遇到嵌套的，递归调用函数，一层一层往里算就可以了，我最先想的方法是遍历给的嵌套链表的数组，对于每个嵌套链表的对象，调用getSum函数，并赋深度值1，累加起来返回。在getSum函数中，首先判断其是否为整数，如果是，则返回当前深度乘以整数，如果不是，那么我们再遍历嵌套数组，对每个嵌套链表再调用递归函数，将返回值累加起来返回即可，

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
               int res = 0;
        
        for(NestedInteger iterm : nestedList){
            res += getSum(iterm,1);
        }
        
        return res;
    }
    
    public int getSum(NestedInteger ni, int level){
        int res = 0;
        
        if(ni.isInteger())
            return ni.getInteger()*level;
        
        for(NestedInteger item : ni.getList()){
            res += getSum(item,level+1);
        }
        
        return res;
    }
}

优化到时间复杂度 o(n),直接在while循环里就进行操作

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
         
        if(nestedList == null || nestedList.size() == 0){
            return 0;
        }
        

        
        //first round offer to queue;

        Queue<NestedInteger> queue = new LinkedList<>();
        
        for(NestedInteger ni : nestedList){
            
                queue.offer(ni);
        }
        
        int level = 1, sum = 0;
        
        while(!queue.isEmpty()){
            int size = queue.size();
            
            int levelSum = 0;
            
            for(int i = 0; i < size;i++){
                NestedInteger ni = queue.poll();
                
                if(ni.isInteger()){
                    levelSum += ni.getInteger()*level;
                }else{
                    for(NestedInteger item : ni.getList()){
                    
                        queue.offer(item);
                    
                    }
                }
                
            }
            
            sum += levelSum;
            level++;
        }
        
        
        
        return sum;
    }
    
   
}

犯的错：

1. levelSum 写到了while循环外面，导致每次循环时 levelSum没有归零

2. while循环内判断item不是数字的时候，直接把item加进了queue，导致了死循环，应该把item的list拿出来，遍历往queue里加