86-二叉查找树迭代器
方法一（空间复杂度O(n)，n为树的节点数）：
使用数组保存树的中序遍历的结果
code
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
* Example of iterate a tree:
* BSTIterator iterator = BSTIterator(root);
* while (iterator.hasNext()) {
* TreeNode * node = iterator.next();
* do something for node
*/
class BSTIterator {
public:
vector<TreeNode *> inorder;
int current;
//@param root: The root of binary tree.
BSTIterator(TreeNode *root) {
// write your code here
inorder = inorderTraversal(root);
current = 0;
}
//@return: True if there has next node, or false
bool hasNext() {
// write your code here
if(current == inorder.size()) {
return false;
}
else {
return true;
}
}
//@return: return next node
TreeNode* next() {
// write your code here
return inorder[current++];
}
vector<TreeNode *> inorderTraversal(TreeNode *root) {
vector<TreeNode *> order;
if(root == NULL) {
return vector<TreeNode *>();
}
stack<TreeNode *> s;
TreeNode *p = root;
while(p != NULL || !s.empty()) {
while(p != NULL) {
s.push(p);
p = p->left;
}
if(!s.empty()) {
p = s.top();
order.push_back(p);
s.pop();
p = p->right;
}
}
return order;
}
};
方法二（空间复杂度O(h)，h为树的高度）：
参考博客http://blog.csdn.net/smile_watermelon/article/details/47280679
code
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
* Example of iterate a tree:
* BSTIterator iterator = BSTIterator(root);
* while (iterator.hasNext()) {
* TreeNode * node = iterator.next();
* do something for node
*/
class BSTIterator {
public:
stack<TreeNode *> inorder;
//@param root: The root of binary tree.
BSTIterator(TreeNode *root) {
// write your code here
putIntoStack(root);
}
//@return: True if there has next node, or false
bool hasNext() {
// write your code here
return !inorder.empty();
}
//@return: return next node
TreeNode* next() {
// write your code here
TreeNode *current = inorder.top();
TreeNode *temp = current;
inorder.pop();
putIntoStack(current->right);
return current;
}
void putIntoStack(TreeNode *root) {
TreeNode *node = root;
while(node != NULL) {
inorder.push(node);
node = node->left;
}
}
};