Meta 二叉树中序迭代器：延迟输出与摊还常数next

题意与假设

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

• 稳定无环二叉树，迭代期间不修改树；不是必须BST，中序输出未必数值有序。
• 训练遵循Python迭代协议，耗尽抛StopIteration；hasNext可用bool(stack)另加接口。

解题路线

1. 初始化沿root.left链push；next弹栈顶node，输出node.val，再把其right子树最左链push。
2. 栈保存接下来尚未访问的祖先与候选，任何左子树都在当前node前输出，右子树最左节点进入栈顶便是其后继。
3. 一次next可能push高度h链，最坏O(h)，但每节点仅push/pop一次，全n次next总O(n)，摊还O(1)。不要将摊还界当单次最坏界。

手动走一遍

树根2左1右4且4左3，初栈[2,1]，next依次1/2/3/4；输出2时才读取并push右子树4/3，没有预先遍历整树。

Python 参考实现

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

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

class InorderIterator:
    """Stable binary tree; mutations during iteration are outside the contract."""
    def __init__(self,root):
        self.stack=[]
        self._push_left(root)
    def _push_left(self,node):
        while node is not None:
            self.stack.append(node);node=node.left
    def __iter__(self):return self
    def __next__(self):
        if not self.stack:raise StopIteration
        node=self.stack.pop();self._push_left(node.right);return node.val

复杂度

初始化O(h)，单次最坏next O(h)/摊还O(1)，全遍历O(n)，栈O(h)。

易错点与追问

容易失分的边界

• 用BFS不能保证左根右；“每层left/root/right”的说法不是中序。
• 初始化把全树flatten会占O(n)，不满足lazy空间目标。

继续深挖

• 逆序迭代器对称保存右链，再进入左子树；双向迭代需保存历史或parent。
• 允许树修改时定义snapshot、fail-fast版本或弱一致，原迭代器不能随意继续并承诺无漏无重。