Chapter 33 Iterator


C++ stack:

33.1 173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average \(O(1)\) time and uses \(O(h)\) memory, where h is the height of the tree.

如果不是题目对space complexity的要求,这题解法根据S分为:

S: O(1) - morris traversal
S: O(H) - stack
S: O(N) - do work at constructor

维护一个栈,从根节点开始,每次迭代地将根节点的左孩子压入栈,直到左孩子为空为止. 调用next()方法时,弹出栈顶,如果被弹出的元素拥有右孩子,则以右孩子为根,将其左孩子迭代压栈.

S:O(N)的解法是: 采用根的中序遍历法将树节点保存在list中也可以实现树的迭代.但是空间复杂度\(O(N)\),N为树的大小,不满足题目要求


33.2 284. Peeking Iterator

If we know the underlying data structure, this question will be very easy. The trikcy part here is you can not access underlying data structure directly, instead you have to use the interface provided by the base class


这里有个C++的语法问题,如何从child class里面调用parent class. 注意这里没有用override,因为没有virtual function. Overload和override的区别?


33.3 341. Flatten Nested List Iterator

这道题让我们建立压平嵌套链表的迭代器,关于嵌套链表的数据结构最早出现在Nested List Weight Sum中,而那道题是用的递归的方法来解的,而迭代器一般都是用迭代的方法来解的,而递归一般都需用栈来辅助遍历,由于栈的后进先出的特性,我们在对向量遍历的时候,从后往前把对象压入栈中,那么第一个对象最后压入栈就会第一个取出来处理,我们的hasNext()函数需要遍历栈,并进行处理,如果栈顶元素是整数,直接返回true,如果不是,那么移除栈顶元素,并开始遍历这个取出的list,还是从后往前压入栈,循环停止条件是栈为空,返回false.

可不可以把push stack的任务放在next()函数中做呢?答案是不可以,因为有edge case: [[]], [[[[]]],[]],如果不对其解封,根本不知道是否有next.






33.4 281. Zigzag Iterator

Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question - Update (2015-09-18): The “Zigzag” order is not clearly defined and is ambiguous for k > 2 cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”. For example, given the following input:


It should return [1,4,8,2,5,9,3,6,7].

33.5 251. Flatten 2D Vector

Implement an iterator to flatten a 2d vector.

For example, Given 2d vector =


By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

  • CPP
  • Java
  • Python

33.6 604. Design Compressed String Iterator

Design and implement a data structure for a compressed string iterator. It should support the following operations: next and hasNext.

The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string.

next() - if the original string still has uncompressed characters, return the next letter; Otherwise return a white space.
hasNext() - Judge whether there is any letter needs to be uncompressed.

Note: Please remember to RESET your class variables declared in StringIterator, as static/class variables are persisted across multiple test cases. Please see here for more details.


StringIterator iterator = new StringIterator("L1e2t1C1o1d1e1");; // return 'L'; // return 'e'; // return 'e'; // return 't'; // return 'C'; // return 'o'; // return 'd'
iterator.hasNext(); // return true; // return 'e'
iterator.hasNext(); // return false; // return ' '