实现一个二叉搜索树的迭代器 BSTIterator。表示一个按中序遍历二叉搜索树(BST)的迭代器:

中序遍历的顺序是:左、根、右。我们使用一个栈来保存节点,以便于迭代的时候取出对应节点。

初始的遍历当前节点的左子树,将其路径上的节点存储到栈中。

调用 next 方法的时候,从栈顶取出节点,因为之前已经将路径上的左子树全部存入了栈中,所以此时该节点的左子树为空,这时候取出节点右子树,再将右子树的左子树进行递归遍历,并将其路径上的节点存储到栈中。

调用 hasNext 的方法的时候,直接判断栈中是否有值即可。