0173.cpp (1093B)
1 // Naive approach using vector to precompute in-order traversal 2 3 class BSTIterator { 4 vector<int> vec; 5 int current = 0; 6 7 public: 8 BSTIterator(TreeNode *root) { 9 stack<TreeNode *> st; 10 while (true) { 11 while (root) { 12 st.push(root); 13 root = root->left; 14 } 15 if (st.empty()) break; 16 root = st.top(); 17 st.pop(); 18 vec.push_back(root->val); 19 root = root->right; 20 } 21 } 22 23 int next() { return vec[current++]; } 24 25 bool hasNext() { return current < vec.size(); } 26 }; 27 28 // Compute in-order on the fly 29 30 class BSTIterator { 31 stack<TreeNode *> st; 32 33 void fill_stack(TreeNode *root) { 34 while (root) { 35 st.push(root); 36 root = root->left; 37 } 38 } 39 40 public: 41 BSTIterator(TreeNode *root) { fill_stack(root); } 42 43 int next() { 44 int val = st.top()->val; 45 TreeNode *root = st.top()->right; 46 st.pop(); 47 fill_stack(root); 48 return val; 49 } 50 51 bool hasNext() { return !st.empty(); } 52 };