栈---二叉搜索树迭代器

1. 题目
   实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
   调用 next() 将返回二叉搜索树中的下一个最小的数。
   注意: next() 和hasNext() 操作的时间复杂度是O(1)，并使用 O(h) 内存，其中 h 是树的高度。
2. 概念
   二叉搜索树概念：
   （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
   （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
   （3）左、右子树也分别为二叉排序树；
   （4）没有键值相等的节点。
3. 代码实现
   方法一：
   a.其实就是要求中序遍历二叉搜索树。

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

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

public class BSTIterator {
    private List<Integer> list;
    private int size;
    private int current;

    /**
     * 中序遍历二叉搜索树
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root!=null||!stack.empty()){
            while (root!=null){
                stack.push(root);
                root = root.left;
            }
            if(!stack.empty()){
                TreeNode top = stack.pop();
                list.add(top.val);
                root = top.right;
            }
        }
        return list;
    }

    public BSTIterator(TreeNode root) {
        //中序遍历二叉搜索树，将元素存入list中
        list = inorderTraversal(root);
        size = list.size();
        current = 0;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return current<size;
    }

    /** @return the next smallest number */
    public int next() {
        int num =list.get(current);
        current++;
        return num;
    }
}

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

方法二：
a.因二叉搜索树的左子树上所有节点的值均小于根节点，首先可将根节点入栈，若左孩子不为空，将其左孩子入栈，左孩子的左孩子入栈。。。。直到其左孩子为空；
b.若出栈一个节点，则可将当前出栈节点的右孩子入栈，出栈节点的右孩子的左孩子。。。依次入栈。
本质还是在中序遍历。

import java.util.Stack;

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

public class BSTIterator_1 {

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

    public BSTIterator_1(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 top = stack.pop();
        if (top.right!=null){
            TreeNode node = top.right;
            while (node!=null){
                stack.push(node);
                node = node.left;
            }
        }
        return top.val;
    }
}

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