正文
✡ leetcode 173. Binary Search Tree Iterator 设计迭代器（搜索树）--------- java
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling
next()
will return the next smallest number in the BST.
Note:
next()
and
hasNext()
should run in average O(1) time and uses O(
h
) memory, where
h
is the height of the tree.
设计一个二叉搜索树的迭代器。要求其中的next()与hasNext()是平均O(1)的时间复杂度，O(h)的空间复杂度，h是树高。
1、用栈来实现，栈中存储的是当前路径的左孩子。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/ public class BSTIterator { Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack();
if (root == null){
return ;
}
while (root != null){
stack.push(root);
root = root.left;
}
} /** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
} /** @return the next smallest number */
public int next() {
TreeNode node = stack.pop();
int ans = node.val;
if (node.right != null){
node = node.right;
while (node != null){
stack.push(node);
node = node.left;
}
}
return ans;
} } /**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
2、用list实现。直接排序然后存储在list中，代码简单高效。（参考discuss）。
这种方法虽然比上面的方法快并且简单，但是使用的空间是O（N)的空间，比上一个多，如果上一个题意中说明该设计类只能用O(h)的空间，那么这种解法就不对了。
ArrayDeque<Integer> list;
public BSTIterator(TreeNode root) {
list = new ArrayDeque<Integer>();
inorderTraverse(root);
}
void inorderTraverse(TreeNode root)
{
if(root == null)
return;
inorderTraverse(root.left);
list.addLast(root.val);
inorderTraverse(root.right);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
if(list.isEmpty())
return false;
else
return true;
}
/** @return the next smallest number */
public int next() {
return list.removeFirst();
}
