Leetcode Q#173
Binary Search Tree Iterator
Solution Strategy:
Task is to implement
Constructor of the iterator
hasnext()
next()
Implement an inorder traversal of the tree. Use an “internal” variable to track current index in the inorder array.
Use that to implement hasnext() and next() methods.
Complexity: Time O(n), Space O(n)
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class BSTIterator { public: BSTIterator(TreeNode *root) { mNode = root; inOrderTraversal(mInorderNodes, root); if(mInorderNodes.size()) { curIndex = -1; } } /** @return whether we have a next smallest number */ bool hasNext() { if (curIndex+1 < mInorderNodes.size()){ return true; } } /** @return the next smallest number */ int next() { if (hasNext()){ int nextElement = mInorderNodes[curIndex + 1]; curIndex++; return nextElement; } return mInorderNodes[curIndex]; } private: void inOrderTraversal(vector& inorderNodes, TreeNode* root){ if(!root) { return;} if (!root->left && !root->right) { inorderNodes.push_back(root->val); return; } inOrderTraversal(inorderNodes, root->left); inorderNodes.push_back(root->val); inOrderTraversal(inorderNodes, root->right); return; } TreeNode* mNode; vector mInorderNodes; int curIndex; }; /** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */