Concise C++ without storing all values at initialization


  • 19
    T
    class NestedIterator {
    private:
        stack<NestedInteger> nodes;
        
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            int size = nestedList.size();
            for(int i = size - 1; i >= 0; --i) {
                nodes.push(nestedList[i]);
            }
        }
    
    int next() {
        int result = nodes.top().getInteger();
        nodes.pop();
        return result;
    }
    
    bool hasNext() {
        while(!nodes.empty()) {
            NestedInteger curr = nodes.top();
            if(curr.isInteger()) {
                return true;
            }
            
            nodes.pop();
            vector<NestedInteger>& adjs = curr.getList();
            int size = adjs.size();
            for(int i = size - 1; i >= 0; --i) {
                nodes.push(adjs[i]);
            }
        }
        
        return false;
        }
    };
    

    The same idea as a DFS, the only tricky part probably is you have to find a value node to claim there is next. And to do that, you have to look through all the nodes in the worst case in the entire graph. So you just keep going until you find a value node; if you can't, there is no next.


  • 0
    T

    HI, thanks for your great solution! Just want to ask you why you can use
    int size = nestedList.size();
    nestedList is NestedInteger class, and in the definition it doesn't mention a size() method ...


  • 0
    E

    because nestedList is a vector, and vector has size function


  • 0
    E

    I like your solution!! Just a small suggestion: maybe should add hasNext() in the first line of next(). Looks like all the test case call hasNext() before next(), but I think it is possible that next if called before hasNext? And if the top of stack is a NestedInteger, it will errors.


  • 0
    S

    @TarzanNJane nestedList is vector class...


  • 0
    Y

    It's a smart and concise solution, but it may consume larger memory. Each stack push will copy all the content of NestedInteger, which potentially has very deep nest. Similarly NestedInteger curr = nodes.top() might also be memory costy. The algorithm also has partially duplicated memory layout.

    Correct me if I'm wrong.


Log in to reply
 

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