173. Binary Search Tree Iterator
题目:
https://leetcode.com/problems/binary-search-tree-iterator/
难度:
Medium
同样没有听题目要求，一开始就取巧，用InOrder，这样得到BSF有序排列，然后使用
class BSTIterator(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
self.root = root
self.lst = []
self.inOrder(root)
self.lst.reverse()
def hasNext(self):
"""
:rtype: bool
"""
return self.lst != []
def next(self):
"""
:rtype: int
"""
return self.lst.pop()
def inOrder(self, root):
if root == None:
return
self.inOrder(root.left)
self.lst.append(root.val)
self.inOrder(root.right)
谷歌了一下，得到如何满足题目要求的hint，从root开始，往左走，把左孩子压入stack，直到左边为空。
然后开始取node，如果node有右孩子，则同样要把node的左孩子入stack，画了一个图，可行。
class BSTIterator(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
self.root = root
self.stack = []
self.pushLeft(root)
def hasNext(self):
"""
:rtype: bool
"""
return self.stack != []
def next(self):
"""
:rtype: int
"""
while self.hasNext():
cur = self.stack.pop()
if cur.right:
self.pushLeft(cur.right)
return cur.val
def pushLeft(self, node):
"""
:type node: TreeNode
"""
cur = node
while cur:
self.stack.append(cur)
cur = cur.left
