Leetcode:Binary Search Tree Iterator

    最近真是各种私事，也顺便给自己懒惰的机会了。

今天开始要继续坚持！

    看了这道题，顿时觉得自己太挫，Binary Search Tree居然不知道是什么。赶紧百度搜索了下。下面这篇文章其实就挺简单易懂的。不知道的童鞋学习下。http://www.cnblogs.com/elaron/archive/2013/04/11/3015155.htm。

    Binary Search Tree，即二叉搜索树，其各种结构定义如下：

    即经过中序遍历即可得到树的元素的从小到大的排序序列。由于题目要求时间复杂度为O(1)，所以得想想办法。

    解题思路是遍历寻找树中的最小节点，即树中最左边的节点。而下一次寻找（下一个最小节点），则相当于在删除该节点的树中寻找最左边的节点，而该节点已经是最左边的节点，即其没有左孩子，则只需要将其右孩子移植到该位置即可（具体删除节点的规则，参见上文说的转载的文章），而其右孩子的最左边的节点即为所求。具体做法是：维护一个栈，从根节点开始，每次压入根节点的左节点，所以其栈顶的元素永远为树中最小的元素节点。当弹出一个元素后，判断该节点是否有右节点，如果有右节点，则将其以其右节点为根节点，继续压入堆栈中。

    不知道说清楚没有，不过对照着代码看解释应该可以看懂的吧，呵呵~这个说话水平有待提高！

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Stack;
public class BSTIterator {

    private Stack<TreeNode> stack=new Stack<TreeNode>();
    public BSTIterator(TreeNode root) {
        while(root!=null){
            stack.push(root);
            root=root.left;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(stack.isEmpty()){
            return false;
        }
        else{
            return true;
        }
    }

    /** @return the next smallest number */
    public int next() {
        if(stack.isEmpty()){
	            return -1;
	        }
	        else{
	            TreeNode temp=stack.pop();
	            TreeNode tempRight=temp.right;
	            while(tempRight!=null){
	            	stack.push(tempRight);
	            	tempRight=tempRight.left;
            	}
	            return temp.val;
	        }
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */