与二叉树的中序遍历(非递归)相似, 以一个数组来存储stand-by的节点, 以root和stack来判定是否hasNext(), 当hasNext()为True的时候, 如果root为None, 则从stack中提取下一个节点, 如果root的左子树不为空, 则1, 将左儿子保存, 2, 将当前节点的左儿子设置为None, 3, 将当前节点存入stack中, 4, 将当前节点的左儿子设为当前节点; 如果root的左子树为空, 则将root保存准备返还, 然后如果右儿子不为空, 将root节点设为右儿子, 然后返还保存的root节点, 如果右儿子为空, 则返还root的同时, 将root设置为None
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
Example of iterate a tree:
iterator = BSTIterator(root)
while iterator.hasNext():
node = iterator.next()
do something for node
"""
class BSTIterator:
#@param root: The root of binary tree.
def __init__(self, root):
# write your code here
self.stack = []
self.head = root
#@return: True if there has next node, or false
def hasNext(self):
# write your code here
if self.head or self.stack:
return True
return False
#@return: return next node
def next(self):
#write your code here
if not self.head:
self.head = self.stack.pop()
else:
while self.head.left:
t = self.head.left
self.head.left = None
self.stack.append(self.head)
self.head = t
else:
ret = self.head
if self.head.right:
self.head = self.head.right
else:
if self.stack:
self.head = self.stack.pop()
else:
self.head = None
return ret
