题目

• 概述：实现一个二叉搜索树迭代器，实现迭代器的基本功能：

  按树中结点值从小到大的顺序迭代

1. hasNext()：是否存在下一个元素

2. next()：返回下一个元素

   假设每一次next()调用都是合理的

• 要求：

1. 时间复杂度O(1)
2. 空间复杂度O(h)，h为二叉搜索树的高度

• 出处：https://leetcode-cn.com/problems/binary-search-tree-iterator/

思路

• 根据二叉搜索树的特性：左孩子<=根<=右孩子，可以得到它的迭代顺序和中序遍历二叉树的顺序一致，所以可以按照非递归中序遍历二叉树的思路来，同样用栈来实现

• 使用二叉搜索树的根来初始化迭代器，将根入栈

• next()：重复观察栈顶元素

  1. 栈顶元素的左孩子为空或已被访问过，将栈顶元素出栈，返回给迭代器

     1. 栈顶元素的右孩子为空，标记左孩子已被访问过

     2. 栈顶元素的右孩子不为空，将右孩子入栈，标记左孩子未被访问过

  2. 否则，将左孩子入栈，标记左孩子未被访问过

• hasNext()：栈不为空则返回true，反之则返回false

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTIterator {
    private TreeNode mTop;
    private boolean mLeftVisited;
    private LinkedList<TreeNode> mStack = new LinkedList<>(); 

    public BSTIterator(TreeNode root) {
        if (root != null) {
            mStack.push(root);
        }
    }
    
    /** @return the next smallest number */
    public int next() {
        while (!mStack.isEmpty()) {
            mTop = mStack.peek();
            if (mTop.left == null || mLeftVisited) {
                mStack.pop();
                if (mTop.right == null) {
                    mLeftVisited = true;
                } else {
                    mStack.push(mTop.right);
                    mLeftVisited = false;
                }
                break;
            } else {
                mStack.push(mTop.left);
                mLeftVisited = false;
            }
        }
        return mTop.val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !mStack.isEmpty();
    }
}