leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

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 };