c***u
发帖数: 4107 | 1 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.
高人的程序是:
public class BSTIteratorInorder {
private Stack stack = new Stack<>();
public BSTIteratorInorder(TreeNode root) {
pushLeftChildren(root); // find the first node (leftmost) to start,
and store the trace
}
// push all the left subnodes to stack until reaching the first node in
inorder (the leftmost node)
private void pushLeftChildren(TreeNode curr) {
while (curr != null) {
stack.add(curr);
curr = curr.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
/** @return the next smallest number */
public int next() {
if (!hasNext()) throw new NoSuchElementException("All nodes have
been visited");
TreeNode res = stack.pop();
pushLeftChildren(res.right);
return res.val;
}
}
我看说, next() should run in O(1) time, 但是上面这个程序, next()不是O(1)啊.
虽然 res = stack.pop(), return res.val是 O(1), 但是这个next()
函数中间, 还有一个入栈的动作pushLeftChildren(res.right), 这个本身是O(h), 那
next()这个函数整体就是O(h)??? | b*****n
发帖数: 618 | | Q**g
发帖数: 183 | 3 amortized average。每个node最多入栈一次，加上n+1个null指针每个尝试一下怎么都
不会超过O(n)。next n 回平均就是O(1)了。
be
,
【在 c***u 的大作中提到】
: 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.
: 高人的程序是:
: public class BSTIteratorInorder {
: private Stack stack = new Stack<>();
:
: public BSTIteratorInorder(TreeNode root) {
|
|
