No stack, easy c++ solution with recursion


  • 2
    V
    class NestedIterator {
    public:
    	vector<int> res;
    	int k = -1;
    	NestedIterator(vector<NestedInteger> &nestedList) {
    		for (auto i:nestedList) {
    			if (i.isInteger()) {
    				res.push_back(i.getInteger());
    			}
    			else {
    				build(i.getList());
    			}
    		}
    	}
    	void build(const vector<NestedInteger> &nestedList) {
    		for (auto i : nestedList) {
    			if (i.isInteger()) {
    				res.push_back(i.getInteger());
    			}
    			else {
    				build(i.getList());
    			}
    		}
    	}
    	int next() {
    		k++;
    		return res[k];
    	}
    	bool hasNext() {
    		if (k == -1)
    			return res.size() > 0;
    		else {
    			if (k + 1 < res.size())
    				return true;
    		}
    		return false;
    	}
    };

  • 1
    U

    nice one. You can get rid of the for loop inside the constructor and call build directly instead.


  • 0

    I guess this is not a real iterator. ;-)

    class NestedIterator {
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            build(nestedList);
        }
        
        void build(vector<NestedInteger>& list) {
            for (auto ni : list) {
                if (ni.isInteger()) {
                    results.push_back(ni.getInteger());
                } else {
                    build(ni.getList());
                }
            }
        }
    
        int next() {
            return results[index++];
        }
    
        bool hasNext() {
            return index < results.size();
        }
    private:
        vector<int> results;
        int index = 0;
    };

  • 0
    H

    @VoKA this is not an iterator.


Log in to reply
 

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