173. Binary Search Tree Iterator

stack的最顶部就是整个BST的最小值（最左侧的叶子节点），每次pop一个值，都要把该root的right加进去，要熟悉BST的性质，左侧的都比右侧的小详见230题 /**

Definition for binary tree
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
} */

public class BSTIterator { Stack stack = new Stack(); public BSTIterator(TreeNode root) { TreeNode temp = root; while(temp != null) { stack.push(temp); temp = temp.left; } }

/** @return whether we have a next smallest number */
public boolean hasNext() {
    return !stack.isEmpty();
}

/** @return the next smallest number */
public int next() {
    TreeNode n = stack.pop();
    TreeNode r = n.right;
    while(r != null) {
        stack.push(r);
        r = r.left;
    }
    return n.val;
}

}

/**

Your BSTIterator will be called like this:
BSTIterator i = new BSTIterator(root);
while (i.hasNext()) v[f()] = i.next(); */

Shawngbk / Leecode

173. Binary Search Tree Iterator #150