173. 二叉搜索树迭代器 173. 二叉搜索树迭代器
题意
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
将返回二叉搜索树中的下一个最小的数。
- 是树的高度。
- 时，BST 中至少存在一个下一个最小的数。
解题思路
由于题目要求使用O(h)的内存，也就是说不再允许将所有的结点都存储下来再去取，因此那些利用中序遍历将所有结点存储下来的方法都不符合题目的要求，这道题目应该是只存储一部分的结点（比如只存左子结点或者只存右子结点）；
stack只保存左孩子，当最左的孩子出列时，如果它有右孩子，就把它右孩子以及往下的所有左节点压入栈；
实现
stack)