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

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Credits:
Special thanks to  for adding this problem and creating all test cases.

题解：使用Stack，由于BST，中序遍历就是从小到大。

code:

public class BSTIterator {	private Stack
   
     stack = null;	public BSTIterator(TreeNode root) {		stack = new Stack
    
     ();		while (root != null) {			stack.push(root);			root = root.left;		}	}	/** @return whether we have a next smallest number */	public boolean hasNext() {		return !stack.isEmpty();	}	/** @return the next smallest number */	public int next() {				if(hasNext()){			int ret = stack.peek().val;			TreeNode cur = stack.pop();			if(cur.right!=null){				cur = cur.right;				while(cur!=null){					stack.push(cur);					cur = cur.left;				}			}			return ret;		}		return -1;	}}
    
   

转载地址：https://blog.csdn.net/zxdfc/article/details/48787711 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！