二叉树中序遍历迭代器设计：栈模拟递归的艺术

一、问题定义

实现一个二叉树的中序遍历迭代器，支持 next() 和 hasNext() 操作，要求：

• next()：返回中序遍历的下一个节点值
• hasNext()：判断是否还有下一个节点
• 空间复杂度优于 O(n)（不能提前遍历整棵树）

二、核心思路：栈模拟递归

中序遍历的顺序是：左子树 → 根节点 → 右子树。关键在于维护一个栈，保存从当前节点到最左叶子的路径。

算法步骤

1. 初始化：从根节点开始，沿着左子树一路压栈
2. next()：弹出栈顶节点，如果有右子树，将右子树的所有左子节点压栈
3. hasNext()：检查栈是否为空

三、代码实现

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BSTIterator:
    def __init__(self, root: TreeNode):
        self.stack = []
        self._push_left(root)
    
    def _push_left(self, node):
        """将节点及其所有左子节点压栈"""
        while node:
            self.stack.append(node)
            node = node.left
    
    def next(self) -> int:
        """返回下一个最小元素"""
        node = self.stack.pop()
        
        # 如果有右子树，将右子树的左路径压栈
        if node.right:
            self._push_left(node.right)
        
        return node.val
    
    def hasNext(self) -> bool:
        """判断是否还有元素"""
        return len(self.stack) > 0

四、复杂度分析

• 时间复杂度：
  • next()：均摊 O(1)（每个节点最多入栈出栈一次）
  • hasNext()：O(1)
• 空间复杂度：O(h)，h 为树的高度（平衡树时为 O(log n)）

五、执行过程示例

二叉树：
    4
   / \
  2   6
 / \
1   3

初始化：stack = [4, 2, 1]
next() → 1, stack = [4, 2]
next() → 2, stack = [4, 3]
next() → 3, stack = [4]
next() → 4, stack = [6]
next() → 6, stack = []

六、面试追问

Q1: 能否实现前序或后序遍历迭代器？

A: 可以。前序遍历更简单（先访问根再压右左子树），后序遍历需要额外标记节点是否已访问右子树。

Q2: 如何优化到 O(1) 空间？

A: Morris 遍历可以实现 O(1) 空间，但会临时修改树结构（通过线索二叉树）。

Q3: 如果树非常大，如何处理？

A: 可以考虑分块加载、懒加载子树，或使用数据库游标模式。