题目背景

设计迭代器：
class 迭代器{
    public:
    迭代器{

    }
    元素类型 next(){//求下一个

    }
    bool has_next(){//求是否有下一个

    }
}

思路总结

一.从一个中间状态到下一个中间状态的思考较为简单时；
leetcode 251 展开二维向量：给定 vector<vector<int>>，从一个元素遍历到下一个元素

二.从一个中间状态到下一个中间状态的思考很难考虑时；

先考虑把所有结果算出来的方法，可以按照2种方式来处理：

1）先把所有结果算出来存起来，维护一个当前下标来迭代
2）当方法的中间状态可以拆解出来时，考虑从一个中间状态到下一个中间状态的过程，把方法拆解成不同部分

leetcode 173 二叉搜索树迭代器
leetcode 281 之字型迭代器
leetcode 341 扁平化嵌套列表迭代器
leetcode 1286 字母组合迭代器

1.leetcode 173 二叉搜索树迭代器（预先算出中序遍历的序列）

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    vector<int> ans;
    int cur;

    BSTIterator(TreeNode* root) {
        dfs(root);
        cur=0;
    }

    void dfs(TreeNode* root){
        if(root!=NULL){
            dfs(root->left);
            ans.push_back(root->val);
            dfs(root->right);
        }
    }

    /** @return the next smallest number */
    int next() {
        return ans[cur++];
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return cur!=ans.size();
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

方法2：（栈）

 vector<int> in_order(TreeNode* root){
        vector<int> ans;
        stack<TreeNode*> st;
        if(!root) return ans;


        while(cur||!st.empty()){
            while(cur){
                st.push(cur);
                cur=cur->left;
            } 
            cur=st.top();st.pop();
            ans.push(cur->val);//输出时机
            cur=cur->right;
        }

        return ans;
    }

1.迭代器构造函数：
第一次到达“输出时机”所走的代码路径，一直走：

while(cur){
    st.push(cur);
    cur=cur->left;
    } 

2.next函数：
进行输出，并走到下一次输出时机
先执行：

cur=st.top();st.pop();
ans.push(cur->val);//输出时机
cur=cur->right;
}

再一直走：

while(cur){
    st.push(cur);
    cur=cur->left;
    } 

3.has_next
进入循环条件：while(cur||!st.empty())

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class BSTIterator {
public:
    stack<TreeNode*> st;
    BSTIterator(TreeNode *root) {
        TreeNode *cur = root;
        while (cur) {
            st.push(cur);
            cur=cur-> left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !st.empty();
    }

    /** @return the next smallest number */
    int next() {
        TreeNode *cur = st.top();
        st.pop();
        int res = cur -> val;
        cur = cur -> right;
        while (cur) {
            st.push(cur);
            cur = cur -> left;
        }
        return res;
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

2.leetcode 281之字型迭代器

问题：给定两个一维向量，实现迭代器交替返回它们的元素。
例如，给定两个一维向量：
v1=[1，2]
v2=[3，4，5，6]，通过反复调用Next，直到hasNext返回false，
Next返回的元素顺序应该是：[1，3，2，4，5，6]。

后续：如果给你k个一维向量怎么办？您的代码可以扩展到这样的情况下有多好？

对后续问题的澄清-最新情况(2015-09-18)：“锯齿”顺序没有明确定义，对k>2起案件含糊不清。如果“zigzag”在您看来不对，则将“zigzag”替换为“循环”。
例如，鉴于以下投入：
[1，2，3]
[4，5，6，7]
[8，9]
应返回[1，4，8，2，5，9，3，6，7]。

算出所有值的方法：

vector<int> Zigzag(vector<int>& v1, vector<int>& v2){
    vector<int> ans; 
    queue<pair<vector<int>:: iterator, vector<int>:: iterator> > q;
    if(!v1.empty()) q.push(make_pair(v1.begin(), v1.end()));
    if(!v2.empty()) q.push(make_pair(v2.begin(), v2.end()));

    while(!q.empty()){
        vector<int>:: iterator cur_begin = q.front().first;
        vector<int>:: iterator cur_end = q.front().second;
        q.pop();
        ans.push_back(*cur_begin);
        if(cur_begin + 1 != cur_end) q.push(make_pair(cur_begin+1, cur_end));
    }

    return ans;
}

转化为迭代器：

class ZigzagIterator {
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        if(!v1.empty()) q.push(make_pair(v1.begin(), v1.end()));
        if(!v2.empty()) q.push(make_pair(v2.begin(), v2.end()));
    }

    int next() {
        vector<int>:: iterator curB = q.front().first;
        vector<int>:: iterator curE = q.front().second;
        q.pop();
        if(curB + 1 != curE) q.push(make_pair(curB+1, curE));
        return (*curB);
    }

    bool hasNext() {
        return !q.empty();
    }
private:
    queue<pair<vector<int>:: iterator, vector<int>:: iterator> > q;
};

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator i(v1, v2);
 * while (i.hasNext()) cout << i.next();
 */

3.leetcode 341 扁平化嵌套列表迭代器

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

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

 

示例 1:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-nested-list-iterator
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法2.1：先算出所有结果

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

class NestedIterator {
public:
    vector<int> ans;
    int cur=0;
    NestedIterator(vector<NestedInteger> &nestedList) {
        dfs(nestedList);
    }

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

    int next() {
        int res=ans[cur];
        cur++;
        return res;
    }

    bool hasNext() {
        return cur<ans.size();
    }
};

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

4.leetcode 1286 字母组合迭代器

请你设计一个迭代器类，包括以下内容：

一个构造函数，输入参数包括：一个 有序且字符唯一 的字符串 characters（该字符串只包含小写英文字母）和一个数字 combinationLength 。
函数 next() ，按 字典序 返回长度为 combinationLength 的下一个字母组合。
函数 hasNext() ，只有存在长度为 combinationLength 的下一个字母组合时，才返回 True；否则，返回 False。
 

示例：

CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iterator

iterator.next(); // 返回 "ab"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "ac"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "bc"
iterator.hasNext(); // 返回 false
 

提示：

1 <= combinationLength <= characters.length <= 15
每组测试数据最多包含 10^4 次函数调用。
题目保证每次调用函数 next 时都存在下一个字母组合

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/iterator-for-combination
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法2.1：先求出所有结果

class CombinationIterator {
public:
    vector<string> ans;
    int cur;
    CombinationIterator(string characters, int combinationLength) {
        dfs(characters,combinationLength,"",0);
        cur=0;
    }

    void dfs(string characters, int len,string temp,int index){
        if(temp.size()==len){
            ans.push_back(temp);
            return;
        }

        for(int i=index;i<characters.size();i++){
            dfs(characters,len,temp+characters[i],i+1);
        }
    }

    string next() {
        return ans[cur++];
    }

    bool hasNext() {
        return cur<ans.size();
    }
};

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */