173. 二叉搜索树迭代器
两种做法：
- 中序递归遍历：我们可以直接对二叉搜索树做一次完全的递归遍历，获取中序遍历的全部结果并保存在数组中。随后，我们利用得到的数组本身来实现迭代器。
<![CDATA[
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class BSTIterator {
private int idx;
private List<Integer> ls;
public BSTIterator(TreeNode root) {
idx = 0;
ls = new ArrayList<Integer>();
Inordertraversal(root, ls);
}
public int next() {
int ret = ls.get(idx++);
return ret;
}
public boolean hasNext() {
if(idx>=ls.size() || ls.get(idx)==null) return false;
else return true;
}
public void Inordertraversal(TreeNode root, List<Integer> ls){
if(root==null) return;
Inordertraversal(root.left, ls);
ls.add(root.val);
Inordertraversal(root.right,ls);
}
}
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator obj = new BSTIterator(root);
* int param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/
]]>
2. 运用栈来实现：先把所有左子树节点压入栈然后按顺序出栈：
- 先将当前节点的所有左子树压入栈，压到没有为止
- 将最后一个压入的节点弹出（栈顶元素），加入答案
- 将当前弹出的节点作为当前节点，重复步骤一
<![CDATA[
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class BSTIterator {
Deque<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new ArrayDeque<>();
inStack(root);
}
public int next() {
TreeNode temp = stack.pollLast();
int res = temp.val;
temp = temp.right;
inStack(temp);
return res;
}
public void inStack(TreeNode root){
while(root!=null){
stack.addLast(root);
root = root.left;
}
}
public boolean hasNext() {
return !stack.isEmpty();
}
}
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator obj = new BSTIterator(root);
* int param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/
]]>
