173. 二叉搜索树迭代器
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
示例：
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
分析：
迭代器是一种设计模式，提供遍历容器对象的接口。本题要求设计二叉搜索树迭代器，在调用next()方法时返回二叉树中最小的元素。
方法一：扁平化二叉搜索树
利用二叉搜索树中序遍历的特点。在创建迭代器对象时保存中序搜索序列。之后直接对序列进行操作即可。
中序遍历代码：
def inorder(root: TreeNode):
inorder(root.left)
nums.append(root.val)
inorder(root.right)
方法二：受控递归
方法一过多的利用了动态数组（Python中的列表、Go中的切片）本身就是可迭代的性质，且中序遍历无法暂停。我们还可以利用一个辅助函数来实现可暂停的递归，同时支持非动态的数组。
代码（Golang）：
方法一：
type BSTIterator struct {
nums []int
root *TreeNode
}
func Constructor(root *TreeNode) BSTIterator {
nums := make([]int, 0)
inorder(root, &nums)
return BSTIterator{
nums: nums,
root: root,
}
}
/** @return the next smallest number */
func (b *BSTIterator) Next() int {
res := b.nums[0]
b.nums = b.nums[1:]
return res
}
/** @return whether we have a next smallest number */
func (b *BSTIterator) HasNext() bool {
return len(b.nums) > 0
}
func inorder(root *TreeNode, nums *[]int) {
if root == nil {
return
}
inorder(root.Left, nums)
*nums = append(*nums, root.Val)
inorder(root.Right, nums)
}
方法二：
type BSTIterator struct {
stack []*TreeNode
root *TreeNode
}
func Constructor(root *TreeNode) BSTIterator {
stack := make([]*TreeNode, 0)
leftMostInOrder(root, &stack)
return BSTIterator{
stack: stack,
root: root,
}
}
/** @return the next smallest number */
func (b *BSTIterator) Next() int {
topMostNode := b.stack[len(b.stack) - 1]
b.stack = b.stack[:len(b.stack) - 1]
if topMostNode.Right != nil {
leftMostInOrder(topMostNode.Right, &b.stack)
}
return topMostNode.Val
}
/** @return whether we have a next smallest number */
func (b *BSTIterator) HasNext() bool {
return len(b.stack) > 0
}
func leftMostInOrder(root *TreeNode, stack *[]*TreeNode) {
for root != nil {
*stack = append(*stack, root)
root = root.Left
}
}
- 方法二中虽然也利用了动态数组的性质，但是完全可以利用是一个索引来替代这些性质。