首页 > 代码库 > Binary Search Tree Iterator
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.
将非递归的中序遍历分为两部分，第一部分为将左子树上的结点全部压入栈中，第二部分为栈顶元素出栈，同时将栈顶元素的右子树上的结点压入栈中。
C++实现代码：
#include<iostream>#include<new>#include<stack>using namespace std;/** * Definition for binary tree */struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class BSTIterator{public: stack<TreeNode*> st; BSTIterator(TreeNode *root) { while(root) { st.push(root); root=root->left; } } /** @return whether we have a next smallest number */ bool hasNext() { return !st.empty(); } /** @return the next smallest number */ int next() { TreeNode *tmp=NULL; if(!st.empty()) { tmp=st.top(); st.pop(); TreeNode *cur=tmp->right; while(cur) { st.push(cur); cur=cur->left; } } return tmp->val; }};void insert(TreeNode *&root,int val){ if(root==NULL) { root=new TreeNode(val); } else if(val<root->val) insert(root->left,val); else insert(root->right,val);}void createBST(TreeNode *&root){ int i; int arr[10]= {2,4,6,1,3,5,9,8,7,10}; for(i=0; i<10; i++) { insert(root,arr[i]); }}int main(){ TreeNode *root=NULL; createBST(root); BSTIterator s(root); for(int i=0;i<10;i++) cout<<s.next()<<" "; cout<<endl;}
看看非递归的中序遍历。。
Binary Search Tree Iterator
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。