【面试经典 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)$ 。