Leetcode 173 Binary search tree iterator (2022.06.22)

Implement a binary search tree iterator class BSTIterator , Represents a binary search tree traversed in middle order （BST） The iterator ：
BSTIterator(TreeNode root) initialization BSTIterator An object of class .BST The root node root Will be given as part of the constructor . The pointer should be initialized to a value that does not exist in BST Number in , And the number is less than BST Any element in .
boolean hasNext() If there is a number traversing to the right of the pointer , Then return to true ; Otherwise return to false .
int next() Move the pointer to the right , Then return the number at the pointer .
Be careful , The pointer is initialized to a value that does not exist in BST Number in , So for next() The first call of will return BST The smallest element in .

You can assume next() The call is always valid , in other words , When calling next() when ,BST There is at least one next number in the middle order traversal of .

Example ：

Input
[“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

explain

BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // return 3
bSTIterator.next(); // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 20
bSTIterator.hasNext(); // return False

Tips ：

The number of nodes in the tree is in the range [1, 10⁵] Inside
0 <= Node.val <= 10⁶
Call at most 10⁵ Time hasNext and next operation

Advanced ：

Can you design a solution that meets the following conditions ？next() and hasNext() The average time complexity of operation is O(1) , And use O(h) Memory . among h Is the height of the tree .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/binary-search-tree-iterator

C++ Submission ：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class BSTIterator {
    
private:
    TreeNode* cur;
    stack<TreeNode*> stk;
public:
    BSTIterator(TreeNode* root): cur(root) {
    }
    
    int next() {
    
        while (cur != nullptr) {
    
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top();
        stk.pop();
        int ret = cur->val;
        cur = cur->right;
        return ret;
    }
    
    bool hasNext() {
    
        return cur != nullptr || !stk.empty();
    }
};

/** * Your BSTIterator object will be instantiated and called as such: * BSTIterator* obj = new BSTIterator(root); * int param_1 = obj->next(); * bool param_2 = obj->hasNext(); */