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.
**Note: next()
and hasNext()
should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

两种想法，如果你想一开始花点时间遍历整棵树，然后每次读的时候快一点，可以在初始化时就把整个树的节点存下来：

var BSTIterator = function(root) {
    this.data = [];
    this.now = 0;
    if (!root) {
        this.length = 0;
    } else {
        var s = [root];
        var left = root.left;
        while (left) {
            s.push(left);
            left = left.left;
        }
        while(s.length!==0) {
            var cur = s.pop();
            this.data.push(cur.val);
            if (cur.right) {
                s.push(cur.right);
                left = cur.right.left;
                while (left) {
                    s.push(left);
                    left = left.left;
                }
            }
        }
        this.length = this.data.length;
    }
    
};
BSTIterator.prototype.hasNext = function() {
    if (this.now>=this.length)
        return false;
    return true;
};
BSTIterator.prototype.next = function() {
    return this.data[this.now++];
};

如果这棵树很大很大，可以每次调用next时遍历一点点：

var BSTIterator = function(root) {
    this.s = [];
    if (root) {
        this.s = [root];
        var left = root.left;
        while (left) {
            this.s.push(left);
            left = left.left;
        }
    }
};
BSTIterator.prototype.hasNext = function() {
    if (this.s.length===0)
        return false;
    return true;
};

BSTIterator.prototype.next = function() {
    var cur =  this.s.pop();
    if (cur.right) {
        this.s.push(cur.right);
        var left = cur.right.left;
        while (left) {
            this.s.push(left);
            left = left.left;
        }
    }
    return cur.val;
};

这两种方法的思想本质上是一样的，都是利用二叉搜索树的特点