LeetCode 341 Flatten Nested List Iterator

LeetCode

<div>

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

<pre>initialize iterator with nestedList res = [] while iterator.hasNext() append iterator.next() to the end of res return res </pre>

If res matches the expected flattened list, then your code will be judged as correct.

Example 1:

<pre>Input: nestedList = [[1,1],2,[1,1]] Output: [1,1,2,1,1] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1]. </pre>

Example 2:

<pre>Input: nestedList = [1,[4,[6]]] Output: [1,4,6] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6]. </pre>

Constraints:

• 1 <= nestedList.length <= 500
• The values of the integers in the nested list is in the range [-10<sup>6</sup>, 10<sup>6</sup>].

</div>

题目大意：

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

解题思路：

有点似括号题但区别是从前往后读取。用Queue或Stack都可以，插入或删除其一需要反序，删除nestedinteger(=list)后要将它里面所有nestedinteger加入。Queue要从队首加入和删除，Stack要从栈顶加入和删除，用Stack比较方便。

Nested List题目：
LeetCode 341 Flatten Nested List Iterator Iterator - Stack LeetCode 339 Nested List Weight Sum - BFS LeetCode 364 Nested List Weight Sum II - BFS

解题步骤：

1. Iterator题目都是用Stack，比如BST Iterator
2. init和next都可以假设是用int来完成，用reversed加入
3. next或hasNext要迭代到第一个integer为止
4. hasNext和next要对第三步保持一致: next要call self.hasNext()

注意事项：

1. 用Stack，逆序将nestedList中nestedinteger加入到stack，直到栈顶元素为int，hasNext才算结束

Python代码：

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

算法分析：

next操作时间复杂度为O(V/N)或O(1)，空间复杂度O(L + N), N为所有数，V为nested list数，O(N + V)/N. O(1)如果不存在nested list