本文共 1589 字，大约阅读时间需要 5 分钟。

题目：实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

题解一、对其进行遍历，存储

class TreeNode{
   		int val;		TreeNode left;		TreeNode right;		TreeNode(int x){
   			val = x;		}	}		class BSTIterator {
   	    int index;	    ArrayList
   
     list;	    public BSTIterator(TreeNode root) {
   	        this.list = new ArrayList<>();	        this.index = -1;	        this.inorder(root);	    }	    // 先进行中序遍历	    private void inorder(TreeNode root){
   	        if(root==null){
   	            return;	        }	        inorder(root.left);	        list.add(root.val);	        inorder(root.right);	    }	    	    /** @return the next smallest number */	    public int next() {
   	        return list.get(++index);	    }	    	    /** @return whether we have a next smallest number */	    public boolean hasNext() {
   	        return this.index+1 < this.list.size();	    }	}
   

对其进行用栈来存储

class BSTIterator {
   	    // 栈	    Stack
   
     stack;	    public BSTIterator(TreeNode root) {
   	        // 初始化	        stack = new Stack<>();	        this.pre(root);	    }	    // 先存储一部分值	    private void pre(TreeNode root){
   	        while(root!=null){
   	            stack.push(root);	            root = root.left;	        }	    }	    /** @return the next smallest number */	    public int next() {
   	        TreeNode temp = this.stack.pop();	        if(temp.right!=null){
   	            this.pre(temp.right);	        }	        return temp.val;	    }	    	    /** @return whether we have a next smallest number */	    public boolean hasNext() {
   	        return this.stack.size()>0;	    }	}
   

转载地址：http://owwdf.baihongyu.com/