力扣173. 二叉搜索树迭代器

深度优先搜索

• 思路：
  • 遍历二叉搜索树，左子树总比根节点小，右子树总比根节点大；
  • 先深度遍历左子树，然后返回其父节点，然后遍历其右子树节点；
  • 使用栈数据结构存储节点数据，借用其“后进先出”的特点；

/*** 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 != 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();}private:TreeNode* cur;std::stack<TreeNode*> stk;
};/*** 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();*/