问题

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

算法：DFS

嵌套的问题容易联想到DFS。对于每一个NI(Nested Integer), 如果仍然是嵌套的，则继续dfs; 如果是单个数字，则将其放入vecter<int>.

时间复杂度

$O(N)$

代码

```
/
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;

* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;

* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector[HTML_REMOVED] &getList() const;
* };
*/

class NestedIterator {
public:
int i = 0;
vector[HTML_REMOVED] seq;
NestedIterator(vector[HTML_REMOVED] &nestedList) {
dfs(nestedList);
}

void dfs(vector<NestedInteger> &nestedList){
    for(auto t:nestedList){
        if(t.isInteger()){
            seq.push_back(t.getInteger());
        }else{
            dfs(t.getList());
        }
    }
}

int next() {
    return seq[i++];
}

bool hasNext() {
    return i < seq.size();
}

};

/*
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i(nestedList);
* while (i.hasNext()) cout << i.next();
/
```