Meta Nested Iterator：惰性展开与重复HasNext

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练稳定int/list无环树，按左到右DFS返回整数；has_next可重复调用，耗尽next抛StopIteration。用list接口练习，实际NestedInteger封装需适配。
• 同题标签没有披露特定接口变体，本文合同不声称已有原始starter。输入遍历期间不修改。

解题路线

1. constructor仅保存根iterator，不能立即flatten整个输入否则失去惰性与depth空间。_advance遇list进入子iterator、耗尽pop，遇int返回。
2. has_next调用_advance并缓存一项；下一次has_next只查看缓存，next取缓存后清空。EMPTY独立object哨兵，0和负整数不与“没有值”混淆。
3. 直接next且无缓存也可advance，两个调用路径共享核心，避免只有hasNext之后才能next的隐藏要求。
4. 每list iterator耗尽最多一次、每item读取最多一次，因此总遍历O(M)。一次next可能跳过很多空list，不能保证单次最坏O(1)；平均成本按整个结构元素摊销。

手动走一遍

[1,[[],2],0]重复三次has_next仍next返回1，再2、0，最后False；用if cached当bool会把0误认为无缓存，可能跳过它。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

EMPTY=object()

class NestedIterator:
    """Stable nested int/list tree, lazy DFS left-to-right; repeated has_next safe."""
    def __init__(self,nested):self.stack=[iter(nested)];self.cached=EMPTY
    def _advance(self):
        while self.stack:
            try:item=next(self.stack[-1])
            except StopIteration:self.stack.pop();continue
            if type(item) is int:return item
            if isinstance(item,list):self.stack.append(iter(item))
            else:raise TypeError('int/list only')
        raise StopIteration
    def has_next(self):
        if self.cached is EMPTY:
            try:self.cached=self._advance()
            except StopIteration:return False
        return True
    def __iter__(self):return self
    def __next__(self):
        if self.cached is not EMPTY:
            value=self.cached;self.cached=EMPTY;return value
        return self._advance()

复杂度

constructor O(1)，总遍历O(M)、辅助O(depth)加单项缓存。单次查询最坏O(M)经过空结构，若只有少量整数却大量空list，按返回整数摊销也不是固定常数。

易错点与追问

容易失分的边界

• has_next每次推进导致重复调用丢整数。
• eager flatten占O(整数数)空间且初始化扫描全部。

继续深挖

• 边遍历边修改children会怎样影响iterator，是否需snapshot合同？
• 想支持peek多项，需要有界buffer并说明空间/提前消费行为。