力扣 173 二叉搜索树迭代器

题意：给定一个二叉搜索书树，返回他的迭代器

思路：用stack实现树的中序遍历非递归

1. 在构造函数中，把跟节点以及他的所有最左节点都加入stack
2. next：每次stack弹出头节点，并把它返回，同时检查它的右节点是否为空，如果不为空，把右节点以及右节点的所有最左节点都加入stack
3. hasNext：只需检查stack是否为空

思想：树的中序遍历非递归

复杂度：时间O（n)，空间O(h) // h为树高

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack<TreeNode>();
        TreeNode temp = root;
        while(temp != null) {
            stack.add(temp);
            temp = temp.left;
        }
    }
    
    /** @return the next smallest number */
    public int next() {
        TreeNode temp1 = stack.pop();
        TreeNode temp = temp1.right;
        while(temp != null) {
            stack.add(temp);
            temp = temp.left;
        }
        return temp1.val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}