Leetcode 341. 扁平化嵌套列表迭代器（中等）

题目：

首先，现在有一种数据结构 NestedInteger，这个结构中存的数据可能是一个 Integer 整数，也可能是一个 NestedInteger 列表。注意，这个列表里面装着的是 NestedInteger，也就是说这个列表中的每一个元素可能是个整数，可能又是个列表，这样无限递归嵌套下去……

NestedInteger 有如下 API：

/**
 * // 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 &getList() const;
 * };
 */

我们的算法会被输入一个 NestedInteger 列表，我们需要做的就是写一个迭代器类，将这个带有嵌套结构 NestedInteger 的列表「拍平」：

* initialize iterator with nestedList
 * res = []
 * while iterator.hasNext()
 * ?   append iterator.next() to the end of res
 * return res

class NestedIterator {
public:
    NestedIterator(vector &nestedList) {
        flatten(nestedList);
        idx_=0;
    }

    void flatten(vector &nestedList){
        for(auto& i:nestedList){
            if(i.isInteger()){
                data_.push_back(i.getInteger());
            }else{
                flatten(i.getList());
            }
        }
    }
    
    int next() {
        return data_[idx_++];
    }
    
    bool hasNext() {
        return idx_<data_.size();
    }
private:
    vector<int> data_;
    int idx_;
};