题目:
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.
答案
方法1(不符合O(h) space的要求)
List<Integer> list = new ArrayList<Integer>();
int index = 0;
public BSTIterator(TreeNode root) {
preorder(root);
}
private void preorder(TreeNode subroot) {
if(subroot == null) return;
preorder(subroot.left);
list.add(subroot.val);
preorder(subroot.right);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return index < list.size();
}
/** @return the next smallest number */
public int next() {
return list.get(index++);
}
方法2
public class BSTIterator {
Stack<TreeNode> stk = new Stack<TreeNode>();
TreeNode currSmallest;
public BSTIterator(TreeNode root) {
if(root == null) return;
pushleft(root);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return stk.size() > 0;
}
/** @return the next smallest number */
public int next() {
TreeNode top = stk.pop();
int ret = top.val;
pushleft(top.right);
return ret;
}
public void pushleft(TreeNode subroot) {
while(subroot != null) {
stk.push(subroot);
subroot = subroot.left;
}
}
}
