339. 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.

解法要点：

如果是integer，直接计算加到返回值里，如不是，加到queue里继续检测。

API:

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    def __init__(self, value=None):
#        """
#        If value is not specified, initializes an empty list.
#        Otherwise initializes a single integer equal to value.
#        """
#
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def add(self, elem):
#        """
#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#        :rtype void
#        """
#
#    def setInteger(self, value):
#        """
#        Set this NestedInteger to hold a single integer equal to value.
#        :rtype void
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """

我的解法：

class Solution(object):
    def depthSum(self, nestedList):
        """
        :type nestedList: List[NestedInteger]
        :rtype: int
        """
        if nestedList == None:
            return
        self.res = 0
        def search(element, level):
            queue = [element]
            while queue:
                size = len(queue)                
                for i in range(size):
                    n = queue.pop(0)
                    if n.isInteger():
                        self.res += level * n.getInteger()
                    else:
                        for e in n.getList():
                            queue.append(e)
                level += 1
        level = 1    
        for element in nestedList:
            if element.isInteger():
                self.res += level * element.getInteger()
            else:
                search(element, level)
        return self.res

简洁版我的解法：

class Solution(object):
    def depthSum(self, nestedList):
        """
        :type nestedList: List[NestedInteger]
        :rtype: int
        """
        if nestedList == None:
            return
        res = 0
        queue = [nestedList]
        level = 1
        while queue:
            size = len(queue)
            for i in range(size):
                p = queue.pop(0)
                for n in p:
                    if n.isInteger():
                        res += level * n.getInteger()
                    else:
                        queue.append(n.getList())
            level += 1
        return res

答案解法：

class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        return depthSum(nestedList, 1);
    }
    
    public int depthSum(List<NestedInteger> list, int depth){
        int sum = 0;
        for(NestedInteger n : list){
            if(n.isInteger()){
                sum += n.getInteger() * depth;
            }
            else{
                sum += depthSum(n.getList(), depth + 1);
            }
        }
        return sum;        
    }
}