剑指 Offer II 055. 二叉搜索树迭代器｜173. 二叉搜索树迭代器：

实现一个二叉搜索树迭代器类 BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

• BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
• boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
• int next() 将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

样例 1

输入
    inputs = ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
    inputs = [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
    
输出
    [null, 3, 7, true, 9, true, 15, true, 20, false]

解释
    BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
    bSTIterator.next();    // 返回 3
    bSTIterator.next();    // 返回 7
    bSTIterator.hasNext(); // 返回 True
    bSTIterator.next();    // 返回 9
    bSTIterator.hasNext(); // 返回 True
    bSTIterator.next();    // 返回 15
    bSTIterator.hasNext(); // 返回 True
    bSTIterator.next();    // 返回 20
    bSTIterator.hasNext(); // 返回 False

提示

• 树中节点的数目在范围 [1, 105] 内
• 0 <= Node.val <= 106
• 最多调用 105 次 hasNext 和 next 操作

进阶

• 你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。

分析

• 这道算法题考查的就是从 二叉搜索树¹ 中从小到大取值，也就是中序遍历。
• 可以直接在初始化时就完成遍历，把值放入队列等数据结构，之后取值和判空就会很快。
• 但是在初始化时就完成遍历有个缺点，就是如果树很大，但是取值取得比较少，那么开始的初始化就是浪费（道理同 数据延迟加载 和 单例模式的懒汉模式 等），所以我们可以把遍历分摊到每一次取值操作中去。

题解

java

class BSTIterator {
    private TreeNode        cur;
    private Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        cur = root;
        stack = new LinkedList<TreeNode>();
    }

    public int next() {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        int val = cur.val;
        cur = cur.right;
        return val;
    }

    public boolean hasNext() {
        return cur != null || !stack.isEmpty();
    }
}

c

typedef struct {
    struct TreeNode *cur;
    struct StackTreeNode *stack[100000];
    int stackSize;
} BSTIterator;


BSTIterator *bSTIteratorCreate(struct TreeNode *root) {
    BSTIterator *iterator = malloc(sizeof(BSTIterator));
    iterator->cur = root;
    iterator->stackSize = 0;
    return iterator;
}

int bSTIteratorNext(BSTIterator *obj) {
    while (obj->cur != NULL) {
        obj->stack[(obj->stackSize)++] = obj->cur;
        obj->cur = obj->cur->left;
    }
    obj->cur = obj->stack[--(obj->stackSize)];
    int val = obj->cur->val;
    obj->cur = obj->cur->right;
    return val;
}

bool bSTIteratorHasNext(BSTIterator *obj) {
    return obj->cur != NULL || obj->stackSize;
}

void bSTIteratorFree(BSTIterator *obj) {
    free(obj);
}

c++

class BSTIterator {
private:
    TreeNode *cur;
    stack<TreeNode *> stacks;
public:
    BSTIterator(TreeNode *root) : cur(root) {
    }

    int next() {
        while (cur != nullptr) {
            stacks.push(cur);
            cur = cur->left;
        }
        cur = stacks.top();
        stacks.pop();
        int val = cur->val;
        cur = cur->right;
        return val;
    }

    bool hasNext() {
        return cur != nullptr || !stacks.empty();
    }
};

python

class BSTIterator:

    def __init__(self, root: TreeNode):
        self.cur = root
        self.stack = []


    def next(self) -> int:
        while self.cur:
            self.stack.append(self.cur)
            self.cur = self.cur.left
        self.cur = self.stack.pop()
        val = self.cur.val
        self.cur = self.cur.right
        return val

    def hasNext(self) -> bool:
        return True if self.cur or self.stack else False

go

type BSTIterator struct {
    cur   *TreeNode
    stack []*TreeNode
}

func Constructor(root *TreeNode) BSTIterator {
    return BSTIterator{cur: root}
}

func (this *BSTIterator) Next() int {
    for this.cur != nil {
        this.stack = append(this.stack, this.cur)
        this.cur = this.cur.Left
    }
    this.cur, this.stack = this.stack[len(this.stack)-1], this.stack[:len(this.stack)-1]
    val := this.cur.Val
    this.cur = this.cur.Right
    return val
}

func (this *BSTIterator) HasNext() bool {
    return this.cur != nil || len(this.stack) > 0
}

rust

use std::{rc::Rc, cell::RefCell};
struct BSTIterator {
  cur: Option<Rc<RefCell<TreeNode>>>,
  stack: Vec<Rc<RefCell<TreeNode>>>
}

impl BSTIterator {

  fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
    BSTIterator {
      cur: root.clone(),
      stack: Vec::new()
    }
  }

  fn next(&mut self) -> i32 {
    while let Some(n) = self.cur.clone() {
      self.stack.push(n.clone());
      self.cur = n.borrow().left.clone();
    };
    self.cur = self.stack.pop();
    let val = self.cur.clone().unwrap().borrow().val;
    self.cur = self.cur.clone().unwrap().borrow().right.clone();
    val
  }

  fn has_next(&self) -> bool {
    self.cur.is_some() || !self.stack.is_empty()
  }
}

原题传送门：https://leetcode-cn.com/problems/kTOapQ/

原题传送门：https://leetcode-cn.com/problems/binary-search-tree-iterator/

非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~