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.
兩種想法，如果你想一開始花點(diǎn)時(shí)間遍歷整棵樹，然后每次讀的時(shí)候快一點(diǎn)罩引，可以在初始化時(shí)就把整個(gè)樹的節(jié)點(diǎn)存下來：
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++];
};
如果這棵樹很大很大，可以每次調(diào)用next時(shí)遍歷一點(diǎn)點(diǎn)：
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;
};
這兩種方法的思想本質(zhì)上是一樣的叛甫，都是利用二叉搜索樹的特點(diǎn)
