本文主要是介绍Binary Search Tree Iterator问题及解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
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.
问题分析：
由于BST遍历是根的中序遍历，所以我们这里使用一种数据结构stack，先把root及其之后左节点的left依次入栈，每次判断是否有下一个时只需要判断stack是否为空即可，而next()操作则需要取出栈顶元素root，后将root->right及其之后的左节点的left入栈，返回root->val即可。
过程详见代码：
/*** Definition for binary tree* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class BSTIterator {
private:stack<TreeNode*> st;
public:BSTIterator(TreeNode *root) {find_left(root);}/** @return whether we have a next smallest number */bool hasNext() {if (st.empty())return false;return true;}/** @return the next smallest number */int next() {TreeNode* top = st.top();st.pop();if (top->right != NULL)find_left(top->right);return top->val;}/** put all the left child() of root */void find_left(TreeNode* root){TreeNode* p = root;while (p != NULL){st.push(p);p = p->left;}}
};/*** Your BSTIterator will be called like this:* BSTIterator i = BSTIterator(root);* while (i.hasNext()) cout << i.next();*/这篇关于Binary Search Tree Iterator问题及解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
