本文共 1391 字，大约阅读时间需要 4 分钟。

二叉搜索树迭代器实现

问题描述

为了实现一个能够返回二叉搜索树下一个最小数的迭代器，我们可以采用中序遍历的方法。这意味着在构造迭代器时，我们首先遍历树记录下所有节点的值。然后，通过一个指针跟踪当前位置，每次调用 next() 方法时，指针后移并返回对应的值。hasNext() 方法则检查指针是否仍有未访问的元素。

解题思路

这种方法确保了每次 next() 和 hasNext() 的操作时间复杂度为 O(1)，空间复杂度为 O(h)，其中 h 为树的高度。

代码实现

class BSTIterator:    def __init__(self, root):        self.list = []        self.pointer = -1        # Perform in-order traversal to collect all node values        self.mid_order(root)        def mid_order(self, node):        if node is not None:            # Traverse left subtree            if node.left:                self.mid_order(node.left)            # Visit current node            self.list.append(node.value)            # Traverse right subtree            if node.right:                self.mid_order(node.right)        def next(self):        self.pointer += 1        return self.list[self.pointer]        def hasNext(self):        return self.pointer + 1 < len(self.list)

解释：

• mid_order 方法进行递归的中序遍历，将节点值存入 self.list。
• 构造函数 __init__ 初始化迭代器，调用 mid_order 开始收集值。
• next() 方法将 pointer 前进并返回对应的值。
• hasNext() 检查是否还有未访问的元素返回布尔值。

优点：

• 高效性：每次操作时间复杂度为 O(1)，空间复杂度为 O(h)。
• 简洁明了：代码结构简洁，易于理解和维护。
• 预处理只需一次遍历：减少了每次查找的开销。

这种方法适用于需要频繁访问树节点的场景，能够显著提升性能。

转载地址：http://ohgyk.baihongyu.com/