二叉搜索树迭代器 -- 两种解法

1. 中序遍历后将节点保存至链表：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTIterator {

    public BSTIterator(TreeNode root) {
        midOrder(root);
    }
    
    /** @return the next smallest number */
    public int next() {
        if(list != null && list.size() > index){
            return list.get(index++).val;
        }else{
            return -1;
        }
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return (list != null && list.size() > index);
    }
    
    private int index = 0;
    private List<TreeNode> list = new ArrayList<>();
    private void midOrder(TreeNode root){
        if(root != null){
            midOrder(root.left);
            list.add(root);
            midOrder(root.right);
        }
    }
}

/**
 * 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();
 */

2. 用栈来存储左侧节点，实现中序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTIterator {

    Stack<TreeNode> stack = new Stack<>();

    /** 初始化迭代器 */
    public BSTIterator(TreeNode root) {
        // 添加元素
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.empty();
    }

    /** @return the next smallest number */
    public int next() {
        // 获取并弹出最小元素
        TreeNode node = stack.pop();
        int min  = node.val;
        node = node.right;
        // 添加元素被弹出结点的右子树上的较小元素
        while(node!=null){
            stack.push(node);
            node = node.left;
        }
        // 返回最小元素
        return min;
    }
}

/**
 * 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();
 */