/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
因為 inorder 都是有序的, 所以從最小開始（ leftmost
一路 push 到 stack, 這樣取出時, 會從最小開始取出
8 -> root
/
2
/ \
1 4 => [1, 2, 8]
from root, do leftmost to push into stack
stack
1 => pop1
2
8
2 => pop 2 => 4
8
4
8
*/
class BSTIterator {
private Deque<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new ArrayDeque<>();
findMostLeft(root); // add left all first
}
private void findMostLeft(TreeNode node) { // add left all first
while (node != null) {
stack.push(node);
node = node.left;
}
}
public int next() {
TreeNode node = stack.pop();
if (node.right != null) { // if have right subtree
findMostLeft(node.right); // add right node's left all first
}
return node.val;
}
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();
*/
