Iterator

算法思路：

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

注意事项：

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

Python代码：

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

def next(self) -> int:
	if self.hasNext():
		return self.stack.pop()
	return 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]

Iterator题目都是用Stack，比如BST Iterator
init和next都可以假设是用int来完成，用reversed加入
next则要考虑两种情况

class NestedIterator(TestCases):

    def __init__(self, nestedList):
        self.stack = []
        for i in reversed(range(len(nestedList))):
            self.stack.append(nestedList[i])

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

    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            nestedList = self.stack.pop().getList()
            for i in reversed(range(len(nestedList))):
                self.stack.append(nestedList[i])
        return True if self.stack else False

应用题型：

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为复合结构数