nikunjsoni

173

Mar 25th, 2021
75
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class BSTIterator {
  13. public:
  14.     stack<TreeNode *> s;
  15.     TreeNode *curr;
  16.    
  17.     BSTIterator(TreeNode* root) {
  18.         curr = root;
  19.     }
  20.    
  21.     int next() {
  22.         while(curr){
  23.             s.push(curr);
  24.             curr = curr->left;
  25.         }
  26.         TreeNode *tmp = s.top();
  27.         s.pop();
  28.         curr = tmp->right;
  29.         return tmp->val;
  30.     }
  31.    
  32.     bool hasNext() {
  33.         return curr || !s.empty();
  34.     }
  35. };
  36.  
  37. /**
  38.  * Your BSTIterator object will be instantiated and called as such:
  39.  * BSTIterator* obj = new BSTIterator(root);
  40.  * int param_1 = obj->next();
  41.  * bool param_2 = obj->hasNext();
  42.  */
RAW Paste Data