力扣链接：173.二叉搜索树迭代器

难度：⭐⭐

✏️ 方法一：

解题关键词：二叉搜索树、递归

解题思路：使用中序遍历将二叉搜索树扁平化为数组，然后不断移动数组 index。

const dfs = (node: TreeNode | null, res: number[]) => {
  if (node === null) return;

  dfs(node.left, res);
  res.push(node.val);
  dfs(node.right, res);
};

class BSTIterator {
  valueArr: number[] = [];
  index: number = -1;

  // 将二叉搜索树扁平化
  constructor(root: TreeNode | null) {
    dfs(root, this.valueArr);
  }

  // 返回数组中下一个元素
  next(): number {
    return this.valueArr[++this.index];
  }

  // 判断下一个元素是否存在
  hasNext(): boolean {
    return this.index + 1 < this.valueArr.length;
  }
}

✏️ 方法二：

解题关键词：二叉搜索树、中序遍历

解题思路：使用栈非迭代中序遍历将二叉搜索树扁平化为数组，然后不断移动数组 index。

const dfs = (node: TreeNode | null, res: number[]) => {
  // 栈
  const stack: TreeNode[] = [];

  // 栈不为空，还有上面的节点需要处理
  // node 不为空，有前面节点的右节点需要处理
  while (stack.length || node !== null) {
    // 一直往左走
    while (node) {
      stack.push(node);
      node = node.left;
    }

    // 出栈 处理
    node = stack.pop();
    res.push(node.val);

    // 处理右节点
    node = node.right;
  }
};

class BSTIterator {
  valueArr: number[] = [];
  index: number = -1;

  // 将二叉搜索树扁平化
  constructor(root: TreeNode | null) {
    dfs(root, this.valueArr);
  }

  // 返回数组中下一个元素
  next(): number {
    return this.valueArr[++this.index];
  }

  // 判断下一个元素是否存在
  hasNext(): boolean {
    return this.index + 1 < this.valueArr.length;
  }
}