题目描述：

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.

题目大意：

实现一个二叉搜索树（BST）的迭代器。你的迭代器会使用BST的根节点初始化。

调用next()会返回BST中下一个最小的数字。

注意：next()和hasNext()应该满足平均O(1)时间复杂度和O(h)空间复杂度，其中h是树的高度。

解题思路：

维护一个栈，从根节点开始，每次迭代地将根节点的左孩子压入栈，直到左孩子为空为止。

调用next()方法时，弹出栈顶，如果被弹出的元素拥有右孩子，则以右孩子为根，将其左孩子迭代压栈。

另请参阅：https://oj.leetcode.com/discuss/20001/my-solutions-in-3-languages-with-stack

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)
        return top.val
    
    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())

采用根的中序遍历法将树节点保存在list中也可以实现树的迭代

但是空间复杂度O(size)，size为树的大小，不满足题目要求

中序遍历法求解的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.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())

 

本文链接：http://bookshadow.com/weblog/2014/12/31/leetcode-binary-search-tree-iterator/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码