首页 > 代码库 > Binary Search Tree Iterator
Binary Search Tree Iterator
Design an iterator over a binary search tree with the following rules:
- Elements are visited in ascending order (i.e. an in-order traversal)
next()andhasNext()queries run in O(1) time in average.
Example
For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]
10 / 1 11 \ 6 12Challenge
Extra memory usage O(h), h is the height of the tree.
Super Star: Extra memory usage O(1)
Analyse: Recursion.
Runtime: 25ms
1 /** 2 * Definition of TreeNode: 3 * class TreeNode { 4 * public: 5 * int val; 6 * TreeNode *left, *right; 7 * TreeNode(int val) { 8 * this->val = val; 9 * this->left = this->right = NULL;10 * }11 * }12 * Example of iterate a tree:13 * BSTIterator iterator = BSTIterator(root);14 * while (iterator.hasNext()) {15 * TreeNode * node = iterator.next();16 * do something for node17 */18 class BSTIterator {19 public:20 //@param root: The root of binary tree.21 BSTIterator(TreeNode *root) {22 // write your code here23 inorder = inorderTraversal(root);24 index = 0;25 }26 27 //@return: True if there has next node, or false28 bool hasNext() {29 // write your code here30 return index < inorder.size();31 }32 33 //@return: return next node34 TreeNode* next() {35 // write your code here36 if (index >= inorder.size()) return NULL;37 return inorder[index++];38 }39 40 private:41 vector<TreeNode* > inorder;42 int index;43 44 vector<TreeNode* > inorderTraversal(TreeNode* root) {45 vector<TreeNode* > result;46 47 helper(result, root);48 return result;49 }50 51 void helper(vector<TreeNode* >& result, TreeNode* root) {52 if (!root) return;53 54 helper(result, root->left);55 result.push_back(root);56 helper(result, root->right);57 }58 };
Binary Search Tree Iterator
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。