LeetCode刷题实战173：二叉搜索树迭代器-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 二叉搜索树迭代器 ，我们先来看题面：

https://leetcode-cn.com/problems/binary-search-tree-iterator/

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.

boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.

int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

题意

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

样例

解题

https://codingchaozhang.blog.csdn.net/article/details/109497176

思路一：对其进行遍历，存储对其进行用栈来存储

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
      val = x;
    }
  }
  
  class BSTIterator {
      int index;
      ArrayList list;

      public BSTIterator(TreeNode root) {
          this.list = new ArrayList<>();
          this.index = -1;
          this.inorder(root);
      }
      // 先进行中序遍历
      private void inorder(TreeNode root){
          if(root==null){
              return;
          }
          inorder(root.left);
          list.add(root.val);
          inorder(root.right);
      }
      
      /** @return the next smallest number */
      public int next() {
          return list.get(++index);
      }
      
      /** @return whether we have a next smallest number */
      public boolean hasNext() {
          return this.index+1 < this.list.size();
      }
  }

思路二：对其进行用栈来存储

class BSTIterator {

      // 栈
      Stack stack;
      public BSTIterator(TreeNode root) {
          // 初始化
          stack = new Stack<>();
          this.pre(root);
      }
      // 先存储一部分值
      private void pre(TreeNode root){
          while(root!=null){
              stack.push(root);
              root = root.left;
          }
      }
      /** @return the next smallest number */
      public int next() {
          TreeNode temp = this.stack.pop();

          if(temp.right!=null){
              this.pre(temp.right);
          }

          return temp.val;
      }
      
      /** @return whether we have a next smallest number */
      public boolean hasNext() {
          return this.stack.size()>0;
      }
  }