P240. 二叉搜索树迭代器

leetcode 173 lintcode 86 设计 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,给你一棵二叉搜索树,你要为它实现一个迭代器。迭代器中包含两个公有方法,next() 方法返回二叉搜索树中下一个最小的数字,hasNext() 方法返回是否还存在下一个数字。

注意,next() 方法和 hasNext() 方法都要求平均时间复杂度是 O(1),并且额外只能使用 O(h) 的辅助空间。其中,h 是二叉搜索树的高度。另外,你可以假设对 next() 方法的调用总是有效的,即不需要考虑在 next() 方法中处理不存在下一个数字的情况

比如说,给你的二叉搜索树 t 是:

t:
    1
  /   \
 0     4
      / \
     2   8

用 t 初始化迭代器,然后就可以调用 next() 和 hasNext():

BSTIterator it = new BSTIterator(t);
it.next();    //  0
it.next();    //  1
it.next();    //  2
it.hasNext(); // true
it.next();    //  4
it.next();    //  8
it.hasNext(); // false

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。