[LeetCode 173] Binary Search Tree Iterator （Medium）

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Example:

image

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

Note:

• next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
• You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

Solution: Stack

1. 题目要求next()andhasNext()should run in average O(1)， 可以用stack`来保存以root为最大值，比它小的所有节点。
   • 这样每次求hasNext()，只需要判断stack是否为空。
   • next()` ，只需pop栈顶的元素
2. 初始化时，只找比当前root更小的nodes (找root最左边那个边上所有的值)，保证stack里面的值是降序。
3. 每一次next() 时，stack.pop ()。然后还要再看是否还有其他值需要推进stack，因为我们初始化的时候，只推了root最左边的path上node （相当于指考虑了每个left节点），对于这个path上每个node的right child都没有放进去。

         7
       /
     3
   /   \
  1     4

 初始化时，stack中只有：1，3，7. 
 当我们执行了两次next ()以后，stack中剩下：7.  
 此时，如果不把4放进去，直接执行next ()，就会返回7，错误。

所以每一次，执行了next() ，都要把pop出来的这个node的right child的最左边path上node全部推进栈。

while (root != null) {
            nodes.push (root);
            root = root.left;
        }

Code

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

    private Stack<TreeNode> nodes;

    public BSTIterator(TreeNode root) {
        nodes = new Stack<> ();
        generateSmallerNodeTracker (root);
    }
    
    // 只找比当前root更小的nodes，保证stack里面的值是降序
    private void generateSmallerNodeTracker (TreeNode root) {
        while (root != null) {
            nodes.push (root);
            root = root.left;
        }
    }
    
    /** @return the next smallest number */
    public int next() {
        TreeNode smallestNode = nodes.pop ();
        generateSmallerNodeTracker (smallestNode.right);
        
        return smallestNode.val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !nodes.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();
 */