题目链接

二叉搜索树迭代器

题目描述

注意点

• 初始指向根节点
• next()指向中序遍历中的下一个节点

解答思路

• 先中序遍历将节点存储到队列中，根据队列先进先出的特点，在调用next()方法时，返回队尾对应的节点并弹出即可

代码

class BSTIterator {
    Deque<TreeNode> deque;

    public BSTIterator(TreeNode root) {
        deque = new ArrayDeque<>();
        inOrderTree(root);
    }
    
    public int next() {
        TreeNode node = deque.pollLast();
        return node.val;
    }
    
    public boolean hasNext() {
        return !deque.isEmpty();
    }

    public void inOrderTree(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderTree(root.left);
        deque.offerFirst(root);
        inOrderTree(root.right);
    }
}

关键点

• 无