173. Binary Search Tree Iterator
實現 BSTIterator 類，該類表示二叉搜索樹（BST）中序遍歷的迭代器：BSTIterator(TreeNode root)：初始化 BSTIterator 類的對象。BST 的根節點作為構造函數的一部分提供。指針應初始化為小於 BST 中任何元素的不存在的數字。
boolean hasNext()：如果在指針右側存在一個數字，則返回 true，否則返回 false。
int next()：將指針向右移動，然後返回指針處的數字。
請注意，通過將指針初始化為不存在的最小數字，第一次調用 next() 會返回 BST 中的最小元素。
你可以假設 next() 的調用總是有效的。也就是說，在每次調用 next() 時，總會有下一個數字存在於中序遍歷中。
範例 1：
輸入：["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
輸出：[null, 3, 7, true, 9, true, 15, true, 20, false]
解釋：
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); bSTIterator.next(); // 返回 3 bSTIterator.next(); // 返回 7 bSTIterator.hasNext(); // 返回 true bSTIterator.next(); // 返回 9 bSTIterator.hasNext(); // 返回 true bSTIterator.next(); // 返回 15 bSTIterator.hasNext(); // 返回 true bSTIterator.next(); // 返回 20 bSTIterator.hasNext(); // 返回 false
約束條件：樹中節點的數量範圍為 [1, 10^5]。
0 <= Node.val <= 10^6。
hasNext 和 next 的調用總次數最多為 10^5。
進階：你能否實現 next() 和 hasNext() 使其平均運行時間為 O(1) 並使用 O(h) 記憶體，其中 h 是樹的高度？
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.stack = []
self._leftmost_inorder(root)
def _leftmost_inorder(self, root):
while root:
self.stack.append(root)
root = root.left
def next(self) -> int:
topmost_node = self.stack.pop()
if topmost_node.right:
self._leftmost_inorder(topmost_node.right)
return topmost_node.val
def hasNext(self) -> bool:
return len(self.stack) > 0
22.5MB, 64ms
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class BSTIterator {
private:
stack<TreeNode*> st;
void leftmostInorder(TreeNode* root) {
while (root != nullptr) {
st.push(root);
root = root->left;
}
}
public:
BSTIterator(TreeNode* root) {
leftmostInorder(root);
}
int next() {
TreeNode* topmostNode = st.top();
st.pop();
if (topmostNode->right != nullptr) {
leftmostInorder(topmostNode->right);
}
return topmostNode->val;
}
bool hasNext() {
return !st.empty();
}
};
27.78MB, 26ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
*/
var BSTIterator = function(root) {
this.stack = [];
this.leftmostInorder(root);
};
BSTIterator.prototype.leftmostInorder = function(root) {
while (root !== null) {
this.stack.push(root);
root = root.left;
}
};
/**
* @return {number}
*/
BSTIterator.prototype.next = function() {
const topmostNode = this.stack.pop();
if (topmostNode.right !== null) {
this.leftmostInorder(topmostNode.right);
}
return topmostNode.val;
};
/**
* @return {boolean}
*/
BSTIterator.prototype.hasNext = function() {
return this.stack.length > 0;
};
62.30MB, 114ms
