與二叉樹的中序遍歷(非遞歸)相似, 以一個(gè)數(shù)組來存儲(chǔ)stand-by的節(jié)點(diǎn), 以root和stack來判定是否hasNext(), 當(dāng)hasNext()為True的時(shí)候, 如果root為None, 則從stack中提取下一個(gè)節(jié)點(diǎn), 如果root的左子樹不為空, 則1, 將左兒子保存, 2, 將當(dāng)前節(jié)點(diǎn)的左兒子設(shè)置為None, 3, 將當(dāng)前節(jié)點(diǎn)存入stack中, 4, 將當(dāng)前節(jié)點(diǎn)的左兒子設(shè)為當(dāng)前節(jié)點(diǎn); 如果root的左子樹為空, 則將root保存準(zhǔn)備返還, 然后如果右兒子不為空, 將root節(jié)點(diǎn)設(shè)為右兒子, 然后返還保存的root節(jié)點(diǎn), 如果右兒子為空, 則返還root的同時(shí), 將root設(shè)置為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
