拓展：惰性展开多叉树

今天来讲一道非常有启发性的设计题目，为什么说它有启发性，我们后面再说。

一、题目描述

这是力扣第 341 题「扁平化嵌套列表迭代器」，我来描述一下题目：

首先，现在有一种数据结构 NestedInteger，这个结构中存的数据可能是一个 Integer 整数，也可能是一个 NestedInteger 列表。注意，这个列表里面装着的是 NestedInteger，也就是说这个列表中的每一个元素可能是个整数，可能又是个列表，这样无限递归嵌套下去……

NestedInteger 有如下 API：

public class NestedInteger {
    // 如果其中存的是一个整数，则返回 true，否则返回 false
    public boolean isInteger();

    // 如果其中存的是一个整数，则返回这个整数，否则返回 null
    public Integer getInteger();

    // 如果其中存的是一个列表，则返回这个列表，否则返回 null
    public List<NestedInteger> getList();
}

class NestedInteger {
public:
    // 如果其中存的是一个整数，则返回 true，否则返回 false
    bool isInteger();

    // 如果其中存的是一个整数，则返回这个整数，否则返回 null
    int getInteger();

    // 如果其中存的是一个列表，则返回这个列表，否则返回 null
    vector<NestedInteger> getList();
};

class NestedInteger:
    def isInteger(self) -> bool:
        # 如果其中存的是一个整数，则返回 True，否则返回 False
        pass

    def getInteger(self) -> int:
        # 如果其中存的是一个整数，则返回这个整数，否则返回 None
        pass

    def getList(self) -> List['NestedInteger']:
        # 如果其中存的是一个列表，则返回这个列表，否则返回 None
        pass

type NestedInteger struct {}

// 如果其中存的是一个整数，则返回 true，否则返回 false
func (ni NestedInteger) isInteger() bool {}

// 如果其中存的是一个整数，则返回这个整数，否则返回 null
func (ni NestedInteger) getInteger() int {}

// 如果其中存的是一个列表，则返回这个列表，否则返回 null
func (ni NestedInteger) getList() []NestedInteger {}

var NestedInteger = {
    // 如果其中存的是一个整数，则返回 true，否则返回 false
    isInteger: function () {},
    // 如果其中存的是一个整数，则返回这个整数，否则返回 null
    getInteger: function () {},
    // 如果其中存的是一个列表，则返回这个列表，否则返回 null
    getList: function () {}
};

我们的算法会被输入一个 NestedInteger 列表，我们需要做的就是写一个迭代器类，将这个带有嵌套结构 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:
        pass

type 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() {}

我们写的这个类会被这样调用，先调用 hasNext 方法，后调用 next 方法：

NestedIterator i = new NestedIterator(nestedList);
while (i.hasNext())
    print(i.next());

题目给的几个示例如下：

示例 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，输入的列表里有三个 NestedInteger，两个列表型的 NestedInteger 和一个整数型的 NestedInteger。

学过设计模式的朋友应该知道，迭代器也是设计模式的一种，目的就是为调用者屏蔽底层数据结构的细节，简单地通过 hasNext 和 next 方法有序地进行遍历。

为什么说这个题目很有启发性呢？因为我最近在用一款类似印象笔记的软件，叫做 Notion（挺有名的）。这个软件的一个亮点就是「万物皆 block」，比如说标题、页面、表格都是 block。有的 block 甚至可以无限嵌套，这就打破了传统笔记本「文件夹」->「笔记本」->「笔记」的三层结构。

回想这个算法问题，NestedInteger 结构实际上也是一种支持无限嵌套的结构，而且可以同时表示整数和列表两种不同类型，我想 Notion 的核心数据结构 block 估计也是这样的一种设计思路。

那么话说回来，对于这个算法问题，我们怎么解决呢？NestedInteger 结构可以无限嵌套，怎么把这个结构「打平」，为迭代器的调用者屏蔽底层细节，得到扁平化的输出呢？

二、解题思路