Iterator

算法思路：

hasNext, next都涉及计算下一个元素，大部分题目是先计算再返回。只有BST是先返回再计算，因为BST的下一个节点取决于要返回的节点，若返回了，就无法知道下一个节点。

注意事项：

1. hasNext中，while循环找到下一个符合条件的元素
2. next中取值后指针要后移。

Python代码：

def __init__(self):
	self.stack = []
	<add to stack>

def next(self) -> int:
	return self.stack.pop() if self.hasNext() else None

def hasNext(self) -> bool:
	while <until find the next element>:
	   <calculate>
	return <next element>

例子：

LeetCode 341 Flatten Nested List Iterator
实现Nested List的Iterator。Nested List是NestedInteger的数组，NestedInteger可以是int，也可以是Nested List
nestedList = [NestedInteger]
NestedInteger 用isInteger()来判断
-> 2 by getInteger()
-> [2, 3] by getList()

1 记得在next和hasnext去pop不是stack[-1]

2. Iterator题目都是用Stack，比如BST Iterator
3. next或hasNext要迭代到第一个integer为止
4. hasNext和next要对第三步保持一致: next要call self.hasNext()

class NestedIterator(TestCases):

    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        for n in reversed(nestedList):
            self.stack.append(n)
    
    def next(self) -> int:
        return self.stack.pop() if self.hasNext() else None

    
    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            n = self.stack.pop()
            for m in reversed(n.getList()):
                self.stack.append(m)
        return self.stack

应用题型：

LeetCode 251 Flatten 2D Vector LeetCode 281 Zigzag Iterator LeetCode 341 Flatten Nested List Iterator LeetCode 173 Binary Search Tree Iterator

算法分析：

next操作时间复杂度为O(N + V)/N或O(1)，N为所有数，V为复合结构数