leetcode | Binary Search Tree Iterator java[二进制搜索树的迭代器]

　　Binary Search Tree Iterator

　　leetcode 原题链接：https://leetcode.com/problems/binary-search-tree-iterator/

　　题目如图所示：

　　这并不是一道难题，可是初看到这个题的时候还是觉得迷茫。仔细想想，每次输出都是最小的值，而且是一个BST，那不就是把一个inorder traversal的list顺着输出么。那么，这道题就简化为了一道inorder traversal的题目。

　　代码：

　　public class BSTIterator {
　　Listlist;
　　int index = 0;
　　public BSTIterator(TreeNode root) {
　　list = inorder(root);
　　}
　　/** @return whether we have a next smallest number */
　　public boolean hasNext() {
　　if(index < list.size()){
　　return true;
　　}
　　return false;
　　}
　　/** @return the next smallest number */
　　public int next() {
　　return list.get(index++);
　　}
　　public Listinorder(TreeNode root){
　　Listlist = new ArrayList();
　　if(root == null){
　　return list;
　　}
　　TreeNode cur = root;
　　Stackstack = new Stack();
　　while(true) {
　　while(cur != null){
　　stack.push(cur);
　　cur = cur.left;
　　}
　　if(stack.isEmpty()){
　　break;
　　}
　　cur = stack.pop();
　　list.add(cur.val);
　　cur = cur.right;
　　}
　　return list;
　　}
　　}
　　/**
　　* Your BSTIterator will be called like this:
　　* BSTIterator i = new BSTIterator(root);
　　* while (i.hasNext()) v[f()] = i.next();
　　*/