LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 用栈保存中序遍历左侧序列即可

class BSTIterator {
 public:
  BSTIterator(TreeNode* root) {
    TreeNode* t = root;
    while (t) {
      s.emplace(t);
      t = t->left;
    }
  }

  /** @return the next smallest number */
  int next() {
    TreeNode* t = s.top();
    int res = t->val;
    s.pop();
    t = t->right;
    while (t) {
      s.emplace(t);
      t = t->left;
    }
    return res;
  }

  /** @return whether we have a next smallest number */
  bool hasNext() { return !empty(s); }

 private:
  stack<TreeNode*> s;
};