Nested List Weight Sum

深度优先往下探就行了，需要注意层级对数是有影响的

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    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
        """
        result = 0
        for num in nestedList:
            if num.isInteger():
                result += num.getInteger()
            else:
                result += self.getSum(num, 2)

        return result

    def getSum(self, num, level):
        result = 0
        for value in num.getList():
            if value.isInteger():
                result += (value.getInteger() * level)
            else:
                result += (self.getSum(value, level + 1))
        return result

Nested List Weight Sum II

先是用最朴素的想法，即先找出最深的层数，再用层数把第一题的方法重新写一遍的思路实现的

# """
# 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 depthSumInverse(self, nestedList):
        """
        :type nestedList: List[NestedInteger]
        :rtype: int
        """
        maxLevel = 1
        for num in nestedList:
            if not num.isInteger():
                maxLevel = max(maxLevel, self.getLevel(num, 2))

        result = 0
        for num in nestedList:
            if num.isInteger():
                result += (maxLevel * num.getInteger())
            else:
                result += (self.getSum(num, maxLevel - 1))

        return result

    def getLevel(self, num, curLevel):
        result = curLevel
        for value in num.getList():
            if not value.isInteger():
                result = max(result, self.getLevel(value, curLevel + 1))
        return result

    def getSum(self, num, curLevel):
        result = 0
        for value in num.getList():
            if value.isInteger():
                result += (curLevel * value.getInteger())
            else:
                result += self.getSum(value, curLevel - 1)
        return result

这里可以用一个很巧妙的BFS一样的方法做，我们记录当前层的数字并将数字全部加到unweight变量上，然后这个unweight变量会随着层数往上堆，这样就不需要乘级数和找级数了，基本就是剥洋葱思维

class Solution(object):
    def depthSumInverse(self, nestedList):
        """
        :type nestedList: List[NestedInteger]
        :rtype: int
        """
        weight, unweight = 0, 0
        while nestedList:
            nxtList = []
            for num in nestedList:
                if num.isInteger():
                    unweight += num.getInteger()
                else:
                    nxtList.append(num.getList())
            weight += unweight
            nestedList = nxtList
        return weight