Nested List Weight Sum II
Problem: Nested List Weight Sum II
We can store the level when we scan through the nested list, or we can store the number in different slots in a list corresponding to their levels. The real depth can be easily computed with the biggest level known.
Code in Python:
# """
# 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
"""
vals = []
def get_value(nestedList, depth):
if len(vals) < depth:
vals.append([])
for item in nestedList:
if item.isInteger():
vals[depth - 1].append(item.getInteger())
else:
get_value(item.getList(), depth + 1)
get_value(nestedList, 1)
return sum((len(vals) - idx) * sum(vals_item) for idx, vals_item in enumerate(vals))