LeetCode173. 二叉搜索树迭代器

旧城等待， 2022-11-14 10:15 146阅读 0赞

难度：中等  
题目描述：

> 实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：  
> BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。  
> boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。  
> int next()将指针向右移动，然后返回指针处的数字。
> 
> 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
> 
> 你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]  
解题思路：

> 中序遍历二叉树，保留遍历结果在一个数组中，直接输出数组元素

/** * 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:
        vector<int> ans;
        void inorder(TreeNode* r){ 
            if(!r){ 
                return;
            }
            inorder(r->left);
            ans.push_back(r->val);
            inorder(r->right);
        }
        BSTIterator(TreeNode* root) { 
            inorder(root);
        }
        int n=0;
        int next() { 
            return ans[n++];
        }
        bool hasNext() { 
            if(n<ans.size()){ 
                return true;
            }else{ 
                return false;
            }
        }
    };
    
    /** * 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(); */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221022/428a31748365484da6edf22143c687ec.png