C++ stack solution, or depth-first-search solution


  • 1
    X

    Stack Solution:

    class NestedIterator {
        stack<NestedInteger> S;
        int nextElement;
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            if (nestedList.size() == 0) return;
            // push into stack reversely
            for (int i = nestedList.size() - 1; i >= 0; i--) {
                S.push(nestedList[i]);
            }
        }
    
        int next() {
            return nextElement;
        }
    
        bool hasNext() {
            while (!S.empty()) {
                NestedInteger current = S.top(); S.pop();
                // if the top element on the stack is an Integer, it is the next element
                if (current.isInteger()) {
                    nextElement = current.getInteger();
                    return true;
                }
                // else access current NestedInteger's List, and push it into the stack
                vector<NestedInteger> nextList = current.getList();
                if (nextList.size() == 0) continue; // corner case: empty list
                for (int i = nextList.size() - 1; i >= 0; i--) {
                    S.push(nextList[i]);
                }
            }
            return false;
        }
    };
    

    Depth-first-search solution:
    Basically the idea is to depth-first-search all elements and push it into a vector, which is much easier to implement.

    class NestedIterator {
        int curIndex;
        vector<int> allElements;
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            curIndex = 0;
            dfs(nestedList, allElements);
        }
        
        void dfs(const vector<NestedInteger> &nestedList, vector<int> &allElements) {
            for (auto N: nestedList) {
                if (N.isInteger()) {
                    allElements.push_back(N.getInteger());
                } else {
                    dfs(N.getList(), allElements);
                }
            }
        }
    
        int next() {
            int res = allElements[curIndex];
            curIndex++;
            return res;
        }
    
        bool hasNext() {
            return curIndex < allElements.size();
        }
    };

Log in to reply
 

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