力扣面试150题--二叉搜索树迭代器

Day 50

题目描述

思路

初次思路：想的比较简单，在构造这个类的时候，直接求出中序遍历，存放在一个数组中，维护一个序号，当然这个不满足进阶做法的空间复杂度，因为需要保存中序遍历的所有值。

/*** 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 {public TreeNode root;public List<TreeNode>mid;int i=0;public BSTIterator(TreeNode root) {mid=new ArrayList<TreeNode>();findmin(root);}public void findmin(TreeNode root){if(root==null){return;}findmin(root.left);mid.add(root);findmin(root.right);}public int next() {int res= mid.get(i).val;i++;return res;}public boolean hasNext() {if(i>=mid.size()){return false;}else{return true;}}
}/*** 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();*/

进阶做法：（题解）
迭代做法，我们知道取得中序遍历可以通过栈来实现，那么就把中序遍历采取非递归写法，每次获取下一个节点，就从栈中取出一个节点，并且处理它后面需要压入栈的节点处理了。这样就满足了进阶的空间复杂度。

class BSTIterator {private TreeNode cur;private Deque<TreeNode> stack;public BSTIterator(TreeNode root) {cur = root;stack = new LinkedList<TreeNode>();}public int next() {while (cur != null) {stack.push(cur);cur = cur.left;}cur = stack.pop();int ret = cur.val;cur = cur.right;return ret;}public boolean hasNext() {return cur != null || !stack.isEmpty();}
}