63-扁平化嵌套列表迭代器

自己的做法

算法思想

写一个递归函数store。

将给定的嵌套整型列表扁平化，存到res列表中。

递归参数：一个待扁平化的嵌套整形列表

返回值：无。

循环该嵌套列表，对于每个列表元素，有两种情况：

1. 该元素是一个整型值，存到res列表中
2. 该元素是一个嵌套列表，递归

该函数执行结束后，就完成了扁平化。

算法实现

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<NestedInteger> &getList() const;
};
class NestedIterator {
private:
    vector<int> res;
    int index = 0;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        store(nestedList);
    }

    void store(const vector<NestedInteger> &nestedList) {
        for(int i = 0; i < nestedList.size(); i++) {
            if(nestedList[i].isInteger()) {
                res.push_back(nestedList[i].getInteger());
            } else {
                store(nestedList[i].getList());
            }
        }
    }

    int next() {
        return res[index++];
    }

    bool hasNext() {
        return index < res.size();
    }
};

性能分析

时间复杂度：$O(n)$，n为res的列表长度，即给定嵌套整型列表的元素个数

空间复杂度：$O(k)$，k为嵌套整型数组的嵌套深度。