341.md

341. Flatten Nested List Iterator

Leetcode link

解题思路

本题的难点在于要怎么把层层嵌套的 list 摊平

在这里我们可以用递归的思路，具体而言就是写一个辅助函数 flatten 来遍历 nestedList：

• 如果是整数的话，就保存起来
• 如果是另一个 list 的话，就把 list 当新的参数递归自己

C++

class NestedIterator {
    private:
    vector<int> res;
  // cpp 为了方便直接给了一个下标辅助遍历结果
    int idx=0;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        flatten(nestedList);
    }
    
    int next() {
        return res[idx++];
    }
    
    bool hasNext() {
        return idx < res.size();
    }
    
    void flatten(vector<NestedInteger> &nestedList) {
        for(int i=0;i<nestedList.size();i++) {
            if(nestedList[i].isInteger()) {
                res.push_back(nestedList[i].getInteger());
            } else {
                flatten(nestedList[i].getList());
            }
        }
    }
};

Javascript

var NestedIterator = function(nestedList) {
    this.res = [];
    flatten(nestedList, this.res);
};

function flatten(nestedList, arr) {
    for(let i=0;i<nestedList.length;i++){
        if(nestedList[i].isInteger()) {
            arr.push(nestedList[i].getInteger());
        } else {
            flatten(nestedList[i].getList(), arr);
        }
    }
}

NestedIterator.prototype.hasNext = function() {
    return this.res.length !== 0;
};

NestedIterator.prototype.next = function() {
    return this.res.shift();
};