# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
class NestedInteger:
   def isInteger(self) -> bool:
       """
       @return True if this NestedInteger holds a single integer, rather than a nested list.
       """
       pass

   def getInteger(self) -> int:
       """
       @return the single integer that this NestedInteger holds, if it holds a single integer
       Return None if this NestedInteger holds a nested list
       """
       pass

   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
       """
       pass

# 这种方法不太好，因为会占用大量存储，不符合迭代器的设计哲学
class NestedIterator:
    def __traverse(self, root: NestedInteger):
        if root.isInteger():
            return [root.getInteger()]
        rtn = []
        for item in root.getList():
            rtn.extend(self.__traverse(item))
        return rtn

    def __init__(self, nestedList: [NestedInteger]):
        self.record = []
        for r in nestedList:
            self.record.extend(self.__traverse(r))
        self.index = 0

    def next(self) -> int:
        rtn = self.record[self.index]
        self.index += 1
        return rtn

    def hasNext(self) -> bool:
        return self.index < len(self.record)

# 这种做法是惰性求值的，但是问题在于会破坏输入的数据，折中的方法是用一个临时存储仅保存一个节点的数据。
class NestedIterator1:
    def __init__(self, nestedList: [NestedInteger]):
        self.nestedList = nestedList
        while len(self.nestedList) > 0 and not self.nestedList[0].isInteger():
            first = self.nestedList[0].getList()
            self.nestedList = first + self.nestedList[1:]

    def next(self) -> int:
        rtn = self.nestedList[0]
        self.nestedList = self.nestedList[1:]
        while len(self.nestedList) > 0 and not self.nestedList[0].isInteger():
            first = self.nestedList[0].getList()
            self.nestedList = first + self.nestedList[1:]
        return rtn

    def hasNext(self) -> bool:
        return len(self.nestedList) > 0

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())