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.

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

Note:next()andhasNext()should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Solution 1: inorder traversal + Stack O(1); O(h)

这道题主要就是考二叉树的中序遍历的非递归形式，需要额外定义一个栈来辅助，二叉搜索树的建树规则就是左<根<右，用中序遍历即可从小到大取出所有节点。

    5
   / \
  3   7
 / \  / \
2   4 6  8

public class BSTIterator {
    Stack<TreeNode> stack = new Stack<>();

    /**
     * Simulate in-order traversal.
     * Push all left descendants (not children) into a Stack to get prepared.
     * A descendant node of a node is any node in the path from that node to the leaf node.
     * The immediate descendant of a node is the “child” node.
     */
    public BSTIterator(TreeNode root) {
        pushLeft(root);
    }


    /** @return whether we have a next smallest number */
    public boolean hasNext() { //If the stack is empty, there is no more node left.
        return !stack.empty();
    }

    /**
    * Imagine all left subtree of a node is popped out.
    * The next will be itself.
    * And then the next will be its right subtree.
    * The right subtree repeats the pattern of pushing all left descendants into a stack.
    */
    //The average time complexity of next() function is O(1) indeed. 
    //As the next function can be called n times at most, 
    //and the pushLeft function handles n nodes in total at these n times
    //in a tree which has n nodes, so the amortized time complexity is O(1).
    //说的不太好：the max number of right nodes in pushLeft(tmpNode.right) function is n 
    /** @return the next smallest number */ 
    public int next() {
        TreeNode node = stack.pop();
        pushLeft(node.right);
        return node.val;
    }

    private void pushLeft(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}