C++ solution using only one stack and builtin iterator without using other data structure


  • 0
    N
    class NestedIterator {
    public:
    
        // the idea is to store the iterator and its end marker at its level to a stack
        // the reason why we need the end marker is that we need to know when the current level traversal is finished
        stack<pair<vector<NestedInteger>::iterator,vector<NestedInteger>::iterator> > st;
    
        NestedIterator(vector<NestedInteger> &nestedList) {
            auto it = nestedList.begin();
            auto end = nestedList.end();
            if(it != end)
                st.push({it,end});
        }
    
        int next() {
            auto p = st.top();
            st.pop();
            int tmp = p.first->getInteger();
            p.first++;
            if(p.first != p.second) // prevents {end,end} to appear in the stack
                st.push({p.first, p.second});
                
            return tmp;
        }
    
        bool hasNext() {
    
            while(!st.empty() && !st.top().first->isInteger() ) {
                auto p = st.top();
                st.pop();
                p.first;
                // first store the next element at this level
                if(p.first != p.second && p.first + 1 != p.second)
                    st.push({p.first+1,p.second});
                // then store the first element at deeper level
                if((p.first->getList()).begin() != (p.first->getList()).end())
                    st.push({(p.first->getList()).begin(), (p.first->getList()).end()});
                    
            }
            return !st.empty();
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.