173. 二叉搜索树迭代器

中等

题目描述

解法：将中序遍历的过程拆分

class BSTIterator {
  // 建立双端队列
    Deque<TreeNode> d = new ArrayDeque<>();
    public BSTIterator(TreeNode root) {
        // 将左节点加入队列中
        dfsLeft(root);
    }
    
    public int next() {
        // 出队
        TreeNode root = d.pollLast();
        int ans = root.val;
        root = root.right;
        dfsLeft(root);
        return ans;
    }

    void dfsLeft(TreeNode root) {
        while (root != null) {
            d.addLast(root);
            root = root.left;
        }
    }
    
    public boolean hasNext() {
        return !d.isEmpty();
    }
}