動機

讓每個遞迴只負責一個工作

Problem

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

  • NestedIterator(List nestedList) Initializes the iterator with the nested list nestedList.
  • int next() Returns the next integer in the nested list.
  • boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedListres = []while iterator.hasNext()    append iterator.next() to the end of resreturn res

If res matches the expected flattened list, then your code will be judged as correct.

 

Example 1:

Input: nestedList = [[1,1],2,[1,1]]Output: [1,1,2,1,1]Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: nestedList = [1,[4,[6]]]Output: [1,4,6]Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

 

Constraints:

  • 1 <= nestedList.length <= 500
  • The values of the integers in the nested list is in the range [-106, 106].

Sol

多一個top，來取目前的值，同時利用裡面的遞迴，去清stack

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stk = [[nestedList,0]] # (list, index)
    
    def top(self):
        if self.stk:
            l, i = self.stk[-1]
            if i < len(l):
                if l[i].isInteger():
                    ret = l[i].getInteger()
                    return ret
                else:
                    self.stk[-1][1] += 1
                    self.stk.append([l[i].getList(),0])
                    return self.top()
            else:
                self.stk.pop()
                return self.top()
        else:
            return False

    def next(self) -> int:
        ret = self.top()
        self.stk[-1][1] += 1
        return ret
    
    def hasNext(self) -> bool:
        return self.top() is not False