首页 > 代码库 > Binary Search Tree Iterator
Binary Search Tree Iterator
QUESTION
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.
1ST TRY
前序遍历，记录下左子树的遍历路径
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */struct MyListNode { TreeNode* node; MyListNode *next; MyListNode(TreeNode* x) : node(x), next(NULL) {}};class BSTIterator {public: BSTIterator(TreeNode *root) { currentRoot = root; leftTree = NULL; buildLeftTree(root); } /** @return whether we have a next smallest number */ bool hasNext() { if(leftTree) return true; else return false; } /** @return the next smallest number */ int next() { ret = leftTree->node->val; tmpListNode = leftTree; leftTree = leftTree->next; buildLeftTree(tmpListNode->node->right); delete[] tmpListNode; return ret; } void buildLeftTree(TreeNode *root) { if(!root) return; tmpTreeNode = root; while(tmpTreeNode) { MyListNode *newListNode = new MyListNode(tmpTreeNode); newListNode->next = leftTree; leftTree = newListNode; tmpTreeNode = tmpTreeNode->left; } }private: TreeNode *tmpTreeNode; TreeNode *currentRoot; MyListNode *tmpListNode; MyListNode *leftTree; int ret; };/** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */
Result: Accepted
Binary Search Tree Iterator
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。