/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
* Example of iterate a tree:
* BSTIterator iterator = new BSTIterator(root);
* while (iterator.hasNext()) {
* TreeNode node = iterator.next();
* do something for node
* }
*/
public class BSTIterator {
private Deque<TreeNode> stack;
private TreeNode next;
/**
* @param root: The root of binary tree.
*/
public BSTIterator(TreeNode root) {
stack = new ArrayDeque<TreeNode>();
next = root;
}
/**
* @return: True if there has next node, or false
*/
public boolean hasNext() {
if (next != null) {
TreeNode curr = next;
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
next = null;
}
return !stack.isEmpty();
}
/**
* @return: return next node
*/
public TreeNode next() {
if (!hasNext())
return null;
TreeNode curr = stack.pop();
next = curr.right;
return curr;
}
}
