Java, 6ms, recursive definition of NestedIterator (no stack), O(height) extra space


  • 0
    S
    public class NestedIterator implements Iterator<Integer> {
    
    List<NestedInteger> nestedList;
    Iterator<NestedInteger> iter;
    NestedInteger curtElem;
    NestedIterator nestedIter;
    
    public NestedIterator(List<NestedInteger> nestedList) {
        this.nestedList = nestedList;
        iter = nestedList.iterator();
    }
    
    
    @Override
    public Integer next() {
        if (curtElem.isInteger()){
            Integer item = curtElem.getInteger();
            curtElem = null;
            return item;
        } else{
            Integer item = nestedIter.next();
            if (!nestedIter.hasNext()){
                curtElem = null;
            }
            return item;
        }
    }
    
    @Override
    public boolean hasNext() {
        // try to assign curtElem
        while (curtElem == null && iter.hasNext()){
            curtElem = iter.next();
            if (curtElem.isInteger()){
                //nestedIter = null;
                return true;
            } else{
                nestedIter = new NestedIterator(curtElem.getList());
                if (nestedIter.hasNext()){
                    return true;
                } else{
                    curtElem = null;
                }
            }
        }
        
        // no need to assign curtElem
        if (curtElem == null){
            return false;
        } else{
            return true; 
        }
       
    }
    

    }


Log in to reply
 

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