LeetCode 173. 二叉搜索树迭代器

题目描述
- 法一：中序遍历 + 存储
法二：迭代(栈)

题目描述

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

地址：https://leetcode-cn.com/problems/binary-search-tree-iterator/
2021/03/28

法一：中序遍历 + 存储
二叉搜索树
中序遍历存储，然后判断输出结果
时间复杂度 O(n)
空间复杂度 O(n)
```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: void inorder(TreeNode root, vector& res) { // 左根右
```
if (!root) {
    return;
}
// 一直往左走，然后存起来
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
```
  }
  
  vector inorderTraver(TreeNode* root) {
```
vector<int> res;
inorder(root, res); // 中序遍历
return res;
```
  }
  
  vector arr; int idx;

public: BSTIterator(TreeNode* root): idx(0), arr(inorderTraver(root)) {}

int next() {
    return arr[idx++];
}
bool hasNext() { // 有元素就返回 true
    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(); */ ```
法二：迭代(栈)

构造方法：一直往左把根节点和子节点的所有左节点放到栈中；
调用 next() 方法时：弹出栈顶的节点；
- 如果它有右子树，则对右子树一路到底，把它和它的所有左节点放到栈中。
时间复杂度 O(1)

空间复杂度 O(h)

class BSTIterator {
private:
  TreeNode* cur;
  stack<TreeNode*> stk;
public:
  BSTIterator(TreeNode* root): cur(root) {}
  int next() {
      while (cur != nullptr) { // 一直往左走
          stk.push(cur);
          cur = cur->left;
      }
      cur = stk.top();
      stk.pop();
      int ret = cur->val;
      cur = cur->right;
      return ret;
  }
  bool hasNext() {
      return cur != nullptr || !stk.empty();
  }
};

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator(object):
  def __init__(self, root):
      self.stack = []
      while root:
          self.stack.append(root)
          root = root.left
  def next(self):
      cur = self.stack.pop()
      node = cur.right
      while node: # 对于右子树也是一直往左走
          self.stack.append(node)
          node = node.left
      return cur.val
  def hasNext(self):
      return len(self.stack) > 0

题目描述

法一：中序遍历 + 存储

法二：迭代(栈)