Binary Search Tree Iterator Solutions in C++
Number 173
Difficulty Medium
Acceptance 56.7%
Link LeetCode
Solutions
C++ solution by haoel/leetcode
// Source : https://oj.leetcode.com/problems/binary-search-tree-iterator/// Author : Hao Chen// Date : 2014-12-31class BSTIterator {private:vector<int> v;int pos;public://Travse the Tree in-order and covert it to an arrayBSTIterator(TreeNode *root) {pos = 0;vector<TreeNode*> stack;while(stack.size()>0 || root !=NULL) {if (root){stack.push_back(root);root = root->left;}else{root = stack.back();stack.pop_back();v.push_back(root->val);root = root->right;}}}/** @return whether we have a next smallest number */bool hasNext() {return pos < v.size();}/** @return the next smallest number */int next() {return v[pos++];}};
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/binary-search-tree-iterator/description//// Author : liuyubobobo/// Time : 2018-06-06#include <iostream>#include <vector>using namespace std;/// Definition for binary treestruct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};/// Using an array to store all the elements////// Time Complexity: initial: O(n)/// hasNext: O(1)/// next: O(1)/// Space Complexity: O(n)class BSTIterator {private:vector<int> data;int nextIndex;public:BSTIterator(TreeNode *root) {data.clear();inOrder(root);nextIndex = 0;}/** @return whether we have a next smallest number */bool hasNext() {return nextIndex < data.size();}/** @return the next smallest number */int next() {return data[nextIndex ++];}private:void inOrder(TreeNode* node){if(node == NULL)return;inOrder(node->left);data.push_back(node->val);inOrder(node->right);}};int main() {return 0;}
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/binary-search-tree-iterator/description//// Author : liuyubobobo/// Time : 2018-06-06#include <iostream>#include <stack>#include <vector>#include <cassert>using namespace std;/// Definition for binary treestruct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};/// Using My Non-recursive Inorder Traversal Algorithm////// Time Complexity: initial: O(1)/// hasNext: O(h)/// next: O(h)/// Space Complexity: O(h)class BSTIterator {private:struct Command{string s; // go, visitTreeNode* node;Command(string s, TreeNode* node): s(s), node(node){}};stack<Command> myStack;public:BSTIterator(TreeNode *root) {if(root != NULL)myStack.push(Command("go", root));}/** @return whether we have a next smallest number */bool hasNext() {while(!myStack.empty()){Command command = myStack.top();myStack.pop();if(command.s == "visit"){myStack.push(command);return true;}else{assert(command.s == "go");if(command.node->right)myStack.push(Command("go",command.node->right));myStack.push(Command("visit", command.node));if(command.node->left)myStack.push(Command("go",command.node->left));}}return false;}/** @return the next smallest number */int next() {while(!myStack.empty()){Command command = myStack.top();myStack.pop();if(command.s == "visit")return command.node->val;else{assert(command.s == "go");if(command.node->right)myStack.push(Command("go",command.node->right));myStack.push(Command("visit", command.node));if(command.node->left)myStack.push(Command("go",command.node->left));}}assert(false);return -1;}};int main() {return 0;}
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/binary-search-tree-iterator/description//// Author : liuyubobobo/// Time : 2018-06-06#include <iostream>#include <stack>#include <vector>#include <cassert>using namespace std;/// Definition for binary treestruct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};/// Using Classic Non-recursive Inorder Traversal Algorithm////// Time Complexity: initial: O(h)/// hasNext: O(1)/// next: O(h)/// Space Complexity: O(h)class BSTIterator {private:stack<TreeNode*> myStack;public:BSTIterator(TreeNode *root) {TreeNode* node = root;while(node != NULL){myStack.push(node);node = node->left;}}/** @return whether we have a next smallest number */bool hasNext() {return !myStack.empty();}/** @return the next smallest number */int next() {assert(hasNext());TreeNode* retNode = myStack.top();myStack.pop();TreeNode* node = retNode->right;while(node != NULL){myStack.push(node);node = node->left;}return retNode->val;}};int main() {return 0;}