拓展：惰性展开多叉树
本文讲解的例题
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 341. Flatten Nested List Iterator | 341. 扁平化嵌套列表迭代器 | 🟠 |
今天来讲一道非常有启发性的设计题目，为什么说它有启发性，我们后面再说。
一、题目描述
这是力扣第 341 题「扁平化嵌套列表迭代器」：
341. 扁平化嵌套列表迭代器 | 力扣 | LeetCode | 🟠
给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。
实现扁平迭代器类 NestedIterator ：
NestedIterator(List<NestedInteger> nestedList)用嵌套列表nestedList初始化迭代器。int next()返回嵌套列表的下一个整数。boolean hasNext()如果仍然存在待迭代的整数，返回true；否则，返回false。
你的代码将会用下述伪代码检测：
initialize iterator with nestedList
res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res
如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。
示例 1：
输入：nestedList = [[1,1],2,[1,1]]
输出：[1,1,2,1,1]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2：
输入：nestedList = [1,[4,[6]]]
输出：[1,4,6]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。
提示：
1 <= nestedList.length <= 500- 嵌套列表中的整数值在范围
[-106, 106]内
我们的算法会被输入一个 NestedInteger 列表，我们需要做的就是写一个迭代器类 NestedIterator，将这个带有嵌套结构 NestedInteger 的列表「拍平」：
public class NestedIterator implements Iterator<Integer> {
// 构造器输入一个 NestedInteger 列表
public NestedIterator(List<NestedInteger> nestedList) {}
// 返回下一个整数
public Integer next() {}
// 是否还有下一个元素？
public boolean hasNext() {}
}class NestedIterator: public Iterator<int> {
public:
// 构造器输入一个 NestedInteger 列表
NestedIterator(vector<NestedInteger> &nestedList) {}
// 返回下一个整数
int next() {}
// 是否还有下一个元素？
bool hasNext() {}
};class NestedIterator:
def __init__(self, nestedList: List[NestedInteger]):
# 构造器输入一个 NestedInteger 列表
pass
# 返回下一个整数
def next(self) -> int:
pass
# 是否还有下一个元素？
def hasNext(self) -> bool:
passtype NestedIterator struct{}
// 构造器输入一个 NestedInteger 列表
func Constructor(nestedList []*NestedInteger) *NestedIterator {}
// 返回下一个整数
func (iter *NestedIterator) Next() int {}
// 是否还有下一个元素？
func (iter *NestedIterator) HasNext() bool {}var NestedIterator = function(nestedList) {
// 构造器输入一个 NestedInteger 列表
}
// 返回下一个整数
NestedIterator.prototype.next = function() {}
// 是否还有下一个元素？
NestedIterator.prototype.hasNext = function() {}我们写的这个 NestedIterator 类会被这样调用，先调用 hasNext 方法，后调用 next 方法：
NestedIterator i = new NestedIterator(nestedList);
while (i.hasNext())
print(i.next());学过设计模式的朋友应该知道，迭代器也是设计模式的一种，目的就是为调用者屏蔽底层数据结构的细节，简单地通过 hasNext 和 next 方法有序地进行遍历。
为什么说这个题目很有启发性呢？因为我最近在用一款类似印象笔记的软件，叫做 Notion（挺有名的）。这个软件的一个亮点就是「万物皆 block」，比如说标题、页面、表格都是 block。有的 block 甚至可以无限嵌套，这就打破了传统笔记本「文件夹」->「笔记本」->「笔记」的三层结构。
回想这个算法问题，NestedInteger 结构实际上也是一种支持无限嵌套的结构，而且可以同时表示整数和列表两种不同类型，我想 Notion 的核心数据结构 block 估计也是这样的一种设计思路。
那么话说回来，对于这个算法问题，我们怎么解决呢？NestedInteger 结构可以无限嵌套，怎么把这个结构「打平」，为迭代器的调用者屏蔽底层细节，得到扁平化的输出呢？