Flatten Nested List Iterator
要点:题的本质是建立next和isInteger/getList/getInteger的关系,考点和tree的遍历类似:用stack存dfs的trace,这样可以backtrack到之前层的结点。
- 注意NestedInteger类的表示,清楚了表示很多题就迎刃而解了:NestedInteger表示一个结点:既可以是List也可以是Integer。什么类型由interface的get method返回值决定。而最外层object是List,这样表示不可能以Integer为起点
- 为什么需要stack?本质上是tree的结构:遍历的时候如果当前元素是list,那么之后要,向更深遍历,并且要能返回的上层继续下一个元素。
- 如何unwind?对于list,相当于子树展开,这里就把list中元素反向push到stack里。因为list可能为空,这样就没有下一个元素可以iterate,所以要多层展开(也就是说,stack top是不能为list的)直到一个integer元素或者没有其他可遍历元素为止。因此,在init和next得到当前元素后,要用prepare来展开stack top的可能list
# """# This is the interface that allows for creating nested lists.# You should not implement it, or speculate about its implementation# """#class NestedInteger(object):# def isInteger(self):# """# @return True if this NestedInteger holds a single integer, rather than a nested list.# :rtype bool# """## def getInteger(self):# """# @return the single integer that this NestedInteger holds, if it holds a single integer# Return None if this NestedInteger holds a nested list# :rtype int# """## def getList(self):# """# @return the nested list that this NestedInteger holds, if it holds a nested list# Return None if this NestedInteger holds a single integer# :rtype List[NestedInteger]# """class NestedIterator(object): def __init__(self, nestedList): """ Initialize your data structure here. :type nestedList: List[NestedInteger] """ self.stk = [] for i in xrange(len(nestedList)-1, -1, -1): self.stk.append(nestedList[i]) self._prepare() def _prepare(self): while self.stk and not self.stk[-1].isInteger(): topList = self.stk.pop().getList() for i in xrange(len(topList)-1, -1, -1): self.stk.append(topList[i]) def next(self): """ :rtype: int """ topInt = self.stk.pop().getInteger() self._prepare() return topInt def hasNext(self): """ :rtype: bool """ return self.stk # Your NestedIterator object will be instantiated and called as such:# i, v = NestedIterator(nestedList), []# while i.hasNext(): v.append(i.next())