题目
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 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()
和hasNext()
操作的时间复杂度是 ,并使用 内存,其中h
是树的高度。- 可以假设
next()
调用总是有效的,也就是说,当调用next()
时,BST 中至少存在一个下一个最小的数。
方案一
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator:
def __init__(self, root: TreeNode):
self._inorder = self.inorderTraversal(root)
self._index = 0
def inorderTraversal(self, node):
if not node:
return []
inorder = []
inorder.extend(self.inorderTraversal(node.left))
inorder.append(node.val)
inorder.extend(self.inorderTraversal(node.right))
return inorder
def next(self) -> int:
"""
@return the next smallest number
"""
self._index += 1
return self._inorder[self._index - 1]
def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""
return len(self._inorder) > self._index
- 先使用中序遍历转化为一个升序列表,在进行处理
方案二(受控递归/手动递归)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator:
def __init__(self, root: TreeNode):
self._stack = []
self._enter_stack_inorder(root)
def _enter_stack_inorder(self, node):
'''
1. 初始化时:将二叉搜索树进栈,保证最上面为最小值
2. 当调用 next() 时,若返回的是非叶子节点且有右节点,则需要调用该函数进行再次入栈
'''
while node:
self._stack.append(node)
node = node.left
def next(self) -> int:
"""
@return the next smallest number
"""
node = self._stack.pop(-1)
if not node:
# 应该报错,由于题目保证,此处暂不做处理
return -1
if node.right:
self._enter_stack_inorder(node.right)
return node.val
def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""
return len(self._stack) > 0