A detailed explanation of the solution from @StefanPochman


  • 0
    2

    This problem is clearly a good problem . But how we can deal with the non-decide-pre recursive times of the nested array .

    The top voted solution is really clever, we just implement it inspired from the ideas of the "syntax analysis" parts of the struct and array design .

    If you have implement a compiler by your self , you will know that when dealing with the recursive structure, we should use the stack to record the level of the current iterator. So we can traverse all the nested elements without missing.

    Based on the above inspiring ideas, you can think of to use the stack to store the start element and end element of the current level nested array. When you have visited all the elements in the current level, you will pop out the begin and end mark iterator

    Here is the ac implementation referred to @StefanPochman

    class NestedIterator {
    public:
        
        NestedIterator(vector<NestedInteger> &nestedList) {
            /** record the current level begin & end iterator **/
            begins.push(nestedList.begin());
            ends.push(nestedList.end());
        }
    
        int next() {
            hasNext();
            return (begins.top()++)->getInteger();
        }
    
        bool hasNext() {
            /** check the begins is not empty **/
            while(begins.size()) {
                /** check the current level elements **/
                /** current begin iterator meet the end iter of the current level **/
                if(begins.top() == ends.top()) {
                    begins.pop();
                    ends.pop();
                } else {
                    auto x = begins.top();
                    if(x->isInteger()) {
                        return true;
                    }
                    /** current iterator points a nested structure **/
                    /** move forward the outter iterator **/
                    begins.top()++;
                    /** push back the nested list begin & end **/
                    begins.push(x->getList().begin());
                    ends.push(x->getList().end());
                }
            }
            return false;
        }
        
        /** store the nested structure **/
        stack<vector<NestedInteger>::iterator> begins, ends;
    };
    
    /**
     * Your NestedIterator object will be instantiated and called as such:
     * NestedIterator i(nestedList);
     * while (i.hasNext()) cout << i.next();
     */

Log in to reply
 

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