# 173. Binary Search Tree Iterator 二叉搜索树迭代器

@TOC

## # 题目描述

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.

Example:

``````BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false
``````

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

Credits: Special thanks to @ts for adding this problem and creating all test cases.

## # 解题方法

### # 保存全部节点

python代码如下：

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

class BSTIterator(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
self.stack = []
self.inOrder(root)

def inOrder(self, root):
if not root:
return
self.inOrder(root.right)
self.stack.append(root.val)
self.inOrder(root.left)

def hasNext(self):
"""
:rtype: bool
"""
return len(self.stack) > 0

def next(self):
"""
:rtype: int
"""
return self.stack.pop()

# 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(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class BSTIterator(object):

def __init__(self, root):
"""
:type root: TreeNode
"""
self.stack = []
self.push_left(root)

def next(self):
"""
@return the next smallest number
:rtype: int
"""
node = self.stack.pop()
self.push_left(node.right)
return node.val

def hasNext(self):
"""
@return whether we have a next smallest number
:rtype: bool
"""
return self.stack

def push_left(self, root):
while root:
self.stack.append(root)
root = root.left

# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
``````

## # 日期

2018 年 3 月 4 日 2019 年 3 月 23 日 —— 周末也要加油呀