萌新刷題（九）二叉查找樹迭代器

題目

設計實現一個帶有下列屬性的二叉查找樹的迭代器：

• 元素按照遞增的順序被訪問（比如中序遍歷）
• next()和hasNext()的詢問操作要求均攤時間複雜度是O(1)

樣例

對於下列二叉查找樹，使用迭代器進行中序遍歷的結果為 [1, 6, 10, 11, 12]

10n / n1 11n n 6 12n

挑戰

額外空間複雜度是O(h)，其中h是這棵樹的高度

Super Star：使用O(1)的額外空間複雜度

思路

先看看什麼是中序遍歷

維護一個棧，從根節點開始，每次迭代地將根節點的左孩子壓入棧，直到左孩子為空為止。

調用next()方法時，彈出棧頂，如果被彈出的元素擁有右孩子，則以右孩子為根，將其左孩子迭代壓棧。

另請參閱：My solutions in 3 languages with Stack

代碼

Python

class BSTIterator:n #@param root: The root of binary tree.n def __init__(self, root):n self.stack = []n self.curt = rootnn #@return: True if there has next node, or falsen def hasNext(self):n return self.curt is not None or len(self.stack) > 0nn #@return: return next noden def next(self):n while self.curt is not None:n self.stack.append(self.curt)n self.curt = self.curt.leftn n self.curt = self.stack.pop()n nxt = self.curtn self.curt = self.curt.rightn return nxtn

廣東校花>..< 廣東高校十大頂級校花，顏值爆表！