【16】二叉搜索树迭代器(LeetCode 173)

问题描述

二叉搜索树迭代器

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。
【16】二叉搜索树迭代器(LeetCode 173)

解题过程

理解题意

emm…说实话我没看懂这个题的要求,或者说不理解什么是迭代器。

所以我首先搜索了一下什么是迭代器:

百度百科:迭代器(iterator)有时又称光标(cursor),是程序设计的软件设计模式,可在容器对象(container,例如链表或数组)上遍访的接口,设计人员无需关心容器对象的内存分配的实现细节。

看了百度百科也不是很理解这题,但是看了题解,又仔细看了示例之后明白了:迭代器说白了就是用来遍历容器的工具,比如本题中需要设计的是一个遍历二叉树的迭代器,每当我们调用迭代器的next()方法时会返回当前二叉树中的最小值,而调用迭代器的hasNext()方法则是返回是否已经遍历完整棵二叉树。

(后来依稀想起来在使用STL时是眼熟过迭代器的,可以结合起来理解)

我们需要完成的就是对next()和hasNext()方法的设计和实现。

解题思路

先说说题解中的第一种思路:

首先,二叉搜索树满足:左子树上所有结点的值均小于它的根结点的值; 右子树上所有结点的值均大于它的根结点的值。

所以对二叉搜索树进行中序遍历,得到的结果就是按照从小到大排序的顺序,如果不记得了可以回顾之前做过的题:验证二叉搜索树

因此,可以将中序遍历的结果按顺序存到一个数组当中,那么每调用一次next()则返回当前索引下的值,并将索引加1(大概就是for(int i=0;i<n;i++)的意思);调用hasNext()就判断当前索引是不是到了最后一个,如果是的话就返回false,否则返回true。

不过在C++里我只知道能开辟一个有限范围的数组:
【16】二叉搜索树迭代器(LeetCode 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 {//二叉搜索树迭代器类
private:
    queue<int> q;//用来存储中序遍历的结果
public:
    BSTIterator(TreeNode* root) {//含参构造函数
        order_(root);
    }
    void order_(TreeNode* root){//中序遍历
        if(root==nullptr)
            return;
        order_(root->left);
        q.push(root->val);
        order_(root->right);
    }
    int next() {
        int result=q.front();
        q.pop();
        return result;
    }
    bool hasNext() {
        return !q.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();
 */

第二种思路之后再补充。

心得

学习STL该提上日程了。

上一篇:与游戏频繁挂钩的SCP是什么?


下一篇:在k8s上安装fluentd收集日志