173. 二叉搜索树迭代器
两种做法:
- 中序递归遍历:我们可以直接对二叉搜索树做一次完全的递归遍历,获取中序遍历的全部结果并保存在数组中。随后,我们利用得到的数组本身来实现迭代器。
/**
* 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 ls;
public BSTIterator(TreeNode root) {
idx = 0;
ls = new ArrayList();
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 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. 运用栈来实现:先把所有左子树节点压入栈然后按顺序出栈:
- 先将当前节点的所有左子树压入栈,压到没有为止
- 将最后一个压入的节点弹出(栈顶元素),加入答案
- 将当前弹出的节点作为当前节点,重复步骤一
/**
* 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 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();
*/