C++ iteration and recursion solution


  • 0
    F
    class NestedIterator {
        using vitr = vector<NestedInteger>::iterator;
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            if (!nestedList.empty())
                stk.push({nestedList.begin(), nestedList.end()});
        }
    
        int next() {
            return cur;
        }
    
        bool hasNext() {
            if (stk.empty()) return false;
            auto p = stk.top();
            if (++stk.top().first == stk.top().second)
                stk.pop();
            if (p.first->isInteger())
            {
                cur = p.first->getInteger();
                return true;
            }
            auto &lst = p.first->getList();
            if (!lst.empty())
                stk.push({lst.begin(), lst.end()});
                
            return hasNext();
        }
    private:
        stack<pair<vitr, vitr>> stk;
        int cur;
    };
    

    As it is a tail recursion, we can easily re-write it using iteration.

    class NestedIterator {
        using vitr = vector<NestedInteger>::iterator;
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            if (!nestedList.empty())
                stk.push({nestedList.begin(), nestedList.end()});
        }
    
        int next() {
            return cur;
        }
    
        bool hasNext() {
            if (stk.empty()) return false;
            
            auto p = stk.top();
            while (true)
            {
                if (++stk.top().first == stk.top().second)
                    stk.pop();
                
                if (p.first->isInteger())
                {
                    cur = p.first->getInteger();
                    return true;
                }
                
                auto &lst = p.first->getList();
                if (!lst.empty())
                    stk.push({lst.begin(), lst.end()});
                    
                if (!stk.empty()) p = stk.top();
                else return false;
            }
        }
    private:
        stack<pair<vitr, vitr>> stk;
        int cur;
    };

Log in to reply
 

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