173 Binary Search Tree Iterator
1. Question
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Callingnext()
will return the next smallest number in the BST.
Note:next()
andhasNext()
should run in average O(1) time and uses O(h) memory, wherehis the height of the tree.
2. Implementation
思路: 其实就是Inorder Traversal分解成next() 和 hasNext()两个function
public class BSTIterator {
TreeNode curNode = null;
Stack<TreeNode> stack = null;
public BSTIterator(TreeNode root) {
curNode = root;
stack = new Stack<>();
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty() || curNode != null;
}
/** @return the next smallest number */
public int next() {
while (curNode != null) {
stack.push(curNode);
curNode = curNode.left;
}
TreeNode temp = stack.pop();
curNode = temp.right;
return temp.val;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
3. Time & Space Complexity
hasNext()时间复杂度是O(1), next()时间复杂度是O(n), 平均时间复杂度是O(1), 空间复杂度是O(h)
Last updated
Was this helpful?