173. Binary Search Tree Iterator
这道题和 tree 非递归 inorder/preorder traversal 一起看。用 stack。
Time = O(n), Space = O(h)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class BSTIterator {
Deque<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new LinkedList<>();
while (root != null) {
stack.offerFirst(root);
root = root.left;
}
}
/** @return the next smallest number */
public int next() {
TreeNode cur = stack.pollFirst();
if (cur.right != null) {
TreeNode rightNode = cur.right;
stack.offerFirst(rightNode);
while (rightNode.left != null) {
stack.offerFirst(rightNode.left);
rightNode = rightNode.left;
}
}
return cur.val;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
}
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator obj = new BSTIterator(root);
* int param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/