Examples of relatively well-fitting shirts (转载)# Fashion - 美丽时尚
c*u
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)???
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
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)???
