## 题目描述：

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

## Python代码：

``````# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class BSTIterator:
# @param root, a binary search tree's root node
def __init__(self, root):
self.stack = []
self.pushLeft(root)

# @return a boolean, whether we have a next smallest number
def hasNext(self):
return self.stack

# @return an integer, the next smallest number
def next(self):
top = self.stack.pop()
self.pushLeft(top.right)

def pushLeft(self, node):
while node:
self.stack.append(node)
node = node.left

# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())
``````

``````# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class BSTIterator:
# @param root, a binary search tree's root node
def __init__(self, root):
self.tree = []
self.inOrderTraverse(root)
self.idx = -1
self.size = len(self.tree)

# @return a boolean, whether we have a next smallest number
def hasNext(self):
self.idx += 1
return self.idx < self.size

# @return an integer, the next smallest number
def next(self):
return self.tree[self.idx]

def inOrderTraverse(self, root):
if root is None:
return
self.inOrderTraverse(root.left)
self.tree.append(root.val)
self.inOrderTraverse(root.right)

# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())
``````

Pingbacks已关闭。

1. 翼灵贰駟 发布于 2016年4月14日 15:32 #

非常不错，思路清晰。而且把其他思路也写出来了，虽然是非最优解，但是可能题目或者假设前提变了的情况下会是一个好方法。