實現一個二叉搜索樹迭代器類BSTIterator ，表示一個按中序遍歷二叉搜索樹（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 類的一個對象。BST 的根節點 root 會作為構造函數的一部分給出。指針應初始化為一個不存在于 BST 中的數字，且該數字小于 BST 中的任何元素。
boolean hasNext() 如果向指針右側遍歷存在數字，則返回 true ；否則返回 false 。
int next()將指針向右移動，然后返回指針處的數字。
注意，指針初始化為一個不存在于 BST 中的數字，所以對 next() 的首次調用將返回 BST 中的最小元素。

可以假設 next() 調用總是有效的，也就是說，當調用 next() 時，BST 的中序遍歷中至少存在一個下一個數字。

示例：

輸入
inputs = [“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
inputs = [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
輸出
[null, 3, 7, true, 9, true, 15, true, 20, false]

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

提示：

樹中節點的數目在范圍 [1, 105] 內
0 <= Node.val <= 106
最多調用 105 次 hasNext 和 next 操作

法一：在構造函數中遞歸計算出中序遍歷的結果：

/*** 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 {
public:BSTIterator(TreeNode* root) {inOrder(root);}int next() {return res[iterator++];}bool hasNext() {return iterator < res.size();}private:vector<int> res;int iterator = 0;void inOrder(TreeNode *node){if (node == nullptr){return;}inOrder(node->left);res.push_back(node->val);inOrder(node->right);}
};/*** 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();*/

如果樹中有n個節點，則此算法時間復雜度為O(n)，隨后每次調用的時間復雜度為O(1)；空間復雜度為O(n)，因為要保存中序遍歷的結果。

法二：迭代法，我們可以用棧模擬遞歸，每次調用next時再計算下一個遍歷的結果：

/*** 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 {
public:BSTIterator(TreeNode* root) { cur = root;}int next() {while (cur){s.push(cur);cur = cur->left;}cur = s.top();int res = cur->val;s.pop();cur = cur->right;return res;}bool hasNext() {return !s.empty() || (cur != nullptr);}private:stack<TreeNode *> s;TreeNode *cur;
};/*** 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();*/

如果樹中有n個節點，每次調用next的時間復雜度最差為O(n)（當樹退化為鏈表時），均攤時間復雜度為O(1)；空間復雜度取決于樹的高度，平均為O(logn)，最差為O(n)。

法三：morris遍歷，核心要點是找到前驅節點，如中序遍歷，需要找到當前遍歷節點的前驅節點，即左節點的最右節點nodeLR，將nodeLR的右節點指向當前遍歷到的節點本身：

/*** 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 {
public:BSTIterator(TreeNode* root) {cur = root;}int next() {while (cur){if (!cur->left){break;}TreeNode *mostRightOfLeft = getMostRightOfLeft(cur);if (!mostRightOfLeft->right){mostRightOfLeft->right = cur;cur = cur->left;}else if (mostRightOfLeft->right == cur){mostRightOfLeft->right = nullptr;break;}}int res = cur->val;cur = cur->right;return res;}bool hasNext() {return cur;}private:TreeNode *cur;TreeNode *getMostRightOfLeft(TreeNode *node){TreeNode *tmpNode = node->left;// 當右節點為空，或右節點是輸入節點時退出循環while (tmpNode->right && tmpNode->right != node){tmpNode = tmpNode->right;}return tmpNode;}
};/*** 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();*/

此算法時間復雜度為O(1)，空間復雜度為O(1)。

法四：二叉搜索，中序遍歷的結果是樹中所有結點從小到大排列，因此每次都找比當前遍歷到的值大的一個節點即可：

/*** 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 {
public:BSTIterator(TreeNode* root) : root(root),cur(nullptr) { }int next() {// 首次運行，找最小值if (!cur){cur = root;while (cur->left){cur = cur->left;}return cur->val;}TreeNode *target = getTarget();cur = target;return target->val;}bool hasNext() {// 首次運行時，是否有下一個取決于是否是空樹if (!cur){return root;}// 如果有比當前值大的，就有下一個節點TreeNode *target = getTarget();return target;}private:TreeNode *root;TreeNode *cur;TreeNode *getTarget(){TreeNode *node = root;TreeNode *res = nullptr;while (node){// 找到比當前值大的一個最小節點if (node->val > cur->val){res = node;node = node->left;}else{node = node->right;}}return res;}
};/*** 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();*/

如果樹有n個節點，此算法next和hasNext函數的時間復雜度為O(logn)，空間復雜度為O(1)。