【3.28】LeetCode每日一题· 二叉搜索树迭代器

2021年03月28日 12时04分

标签： LeetCode 栈树形结构

## 题目描述
实现一个二叉搜索树迭代器类`BSTIterator`，表示一个按中序遍历二叉搜索树（BST）的迭代器：
* `BSTIterator(TreeNode root)`初始化`BSTIterator`类的一个对象。BST 的根节点`root`会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
* `boolean hasNext()`如果向指针右侧遍历存在数字，则返回 `true`；否则返回`false`。
* `int next()`将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对`next()`的首次调用将返回 BST 中的最小元素。

你可以假设`next()`调用总是有效的，也就是说，当调用`next()`时，BST的中序遍历中至少存在一个下一个数字。

#### 示例
![](https://assets.leetcode.com/uploads/2018/12/25/bst-tree.png)
```
输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]

解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // 返回 3
bSTIterator.next();    // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 20
bSTIterator.hasNext(); // 返回 False
```

#### 提示
```
树中节点的数目在范围 [1, 10^5] 内
0 <= Node.val <= 10^6
最多调用 10^5 次 hasNext 和 next 操作
```

#### 进阶
你可以设计一个满足下述条件的解决方案吗？`next()`和`hasNext()`操作均摊时间复杂度为$$O(1)$$，并使用$$O(h)$$内存。其中$$h$$是树的高度。

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/binary-search-tree-iterator "题目链接")

## 扁平化
最简单的，可以想到以**中序遍历**遍历BST，将结果记录在一个一维数组里。然后对一维数组进行迭代即可。

时间复杂度：$$O(n)$$
空间复杂度：因为要保存BST中所有元素的值，因此空间复杂度为$$O(n)$$

public:
    BSTIterator(TreeNode* root) {
        dfs(root);
        it = items.begin();
    }
    
    int next() {
        return *(it++);
    }
    
    bool hasNext() {
        return it != items.end();
    }
};

/**
 * 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();
 */
```

## 用时和内存
> 执行用时：28 ms，在所有 C++提交中击败了91.85%的用户
> 内存消耗：23.7 MB，在所有 C++提交中击败了38.85%的用户

## 栈模拟
由于**中序遍历**时对结点的访问顺序，就是迭代器的顺序，那么我们可不可以仅在需要的时候（也就是调用`next()`方法的时候），才对树进行遍历，即**实时维护当前栈的情况**；而非一次性地将树遍历完，预先计算出中序遍历的全部结果。

我们可以利用**栈**这一数据结构，将递归改成迭代，这样在同一时刻最多只有$$h$$个节点需要保存在栈中，因此空间复杂度是$$O(h)$$的。

具体地，可以采取如下算法：
1. 从BST的根节点开始，不停往左走，每访问到一个节点（包括BST的根节点）就将其压入栈中，直到左子树为空；此时，栈顶节点的值即为迭代器要访问的下一个值。
2. 当调用`next()`时，弹出栈顶节点；并从栈顶节点的右子树的根开始，不停向左走，并将访问的节点（包括右子树的根节点）压入栈中直到左子树为空；
3. `hasNext()`即为判断栈是否为空

均摊时间复杂度：`hasNext()`的时间复杂度显然为$$O(1)$$；$$n$$次调用`next()`函数中，BST中的每个节点至多入栈、出栈一次，因此`next()`的均摊时间复杂度为$$O(1)$$
空间复杂度：栈的深度即为空间复杂度，因此为$$O(h)$$。

### 代码
```cpp
/**
 * 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:
    stack<TreeNode*> items;
    void pushLeft(TreeNode* root){
        if(!root) return;
        items.push(root);
        while(root->left){
            items.push(root->left);
            root = root->left;
        }
    }
public:
    BSTIterator(TreeNode* root) {
        pushLeft(root);
    }
    
    int next() {
        TreeNode* curr = items.top(); items.pop();
        pushLeft(curr->right);
        return curr->val;
    }
    
    bool hasNext() {
        return items.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();
 */
```

## 用时和内存
> 执行用时：24 ms，在所有 C++提交中击败了96.94%的用户
> 内存消耗：23.5 MB，在所有 C++提交中击败了72.30%的用户

所有评论

166****5019 2021年03月28日 23:37:37
测试手机端

参与主题/评论回复

166****5019 发表于2021年03月28日 23:37:37
测试手机端

回复评论

邮箱

图形验证码

邮箱验证码

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.28】LeetCode每日一题· 二叉搜索树迭代器

所有评论

新增评论