【LeetCode题解】173. 二叉搜索树迭代器 LeetCode题解

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
提示：next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。
题解：

对于二叉搜索树来说返回二叉搜索树中的下一个最小的数 = 中序遍历序列
中序遍历 = left - visit - right ，非递归时使用辅助栈
left - visit ：从根结点开始，结点及左子树结点依次入栈
- right：已无左子树或左子树已被访问，弹栈，右子树结点也是一个二叉搜索树的root，递归处理

class BSTIterator { //二叉搜索树 Stack s = new Stack<>(); public BSTIterator(TreeNode root) { // dfs(root); }/** @return the next smallest number */ public int next() { TreeNode tmp = s.pop(); //中序遍历的后半段 -right int ret = tmp.val; if(tmp.right!=null){ //如有右子树，对右子树递归处理 dfs(tmp.right); } return ret; }/** @return whether we have a next smallest number */ public boolean hasNext() { if(!s.empty()){ return true; }else{ return false; } } //中序遍历的前半段 left-visit void dfs(TreeNode root){ while(root!=null){ s.push(root); root = root.left; } } }

【【LeetCode题解】173. 二叉搜索树迭代器】