【面试经典 150 | 二叉树】二叉搜索树迭代器

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：中序遍历到数组
- 方法二：迭代
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【二叉搜索树】【递归】【迭代】

题目来源

173. 二叉搜索树迭代器

解题思路

方法一：中序遍历到数组

思路

设计类，主要两个功能：

一是返回迭代器指针指向当前二叉搜索树中最小节点值；
二是返回迭代器指针当前是否有右侧节点值。

我们知道对于二叉搜索树的中序遍历结果是一个递增的子序列，于是可以利用数组 arr 将其保存。用一个指针 idx （实际上是一个索引）指向数组中元素，调用 next 函数，实际上需要返回的是 arr[i]，记得此时需要更新指针的值，为下一次的调用做准备。

调用 hasNext 函数实际上就是在判断 idx 是否已经超越了 arr 的界限，如果没有则返回 true，否则返回 false。

初始化的工作就需要将二叉搜索树的中序遍历序列化。

代码

/*** 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:void inorder(TreeNode* root, vector<int>& res) {if (!root) {return;}inorder(root->left, res);res.push_back(root->val);inorder(root->right, res);}vector<int> returnInorderRes(TreeNode* root) {vector<int> res;inorder(root, res);return res;}vector<int> arr;int idx;
public:BSTIterator(TreeNode* root): idx(0), arr(returnInorderRes(root)) {}int next() {return arr[idx++];}bool hasNext() {return idx < arr.size();}
};/*** 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 (n)$ ， $n$ 为二叉搜索树中节点的数量。两个成员函数的时间复杂度均为 $O (1)$ 。

空间复杂度： $O (n)$ 。

方法二：迭代

中序遍历可以用递归还实现，也可以使用迭代来实现。利用迭代实现需要借助栈，利用迭代就不需要先将节点值存储下来，可以一般存储一边实现几个成员函数。

代码

/*** 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) {stk.push(cur);cur = cur->left;}cur = stk.top(); stk.pop();int res = cur->val;cur = cur->right;return res;}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();*/

复杂度分析

时间复杂度：初始化和调用 hasNext 都需要时间 $O (1)$ 。每次调用 next 最坏需要 $O (n)$ 时间， $n$ 为二叉搜索树中节点的数量。但考虑到 $n$ 次调用 $\text{next()}$ 函数总共会遍历全部的 $n$ 个节点，因此总的时间复杂度为 $O (n)$ ，因此单次调用平均下来的均摊复杂度为 $O (1)$ 。