Trick: Lazy Expansion of a Multiway Tree

Today, we'll discuss a very insightful design problem. We'll explain why it's insightful later.

1. Problem Description

This is LeetCode problem #341, "Flatten Nested List Iterator." Here's the description:

First, there is a data structure called NestedInteger. This structure can store either an Integer or a list of NestedInteger. Note that this list contains NestedInteger objects, meaning each element in the list can be an integer or another list, leading to potentially infinite recursive nesting.

The NestedInteger has the following API:

public class NestedInteger {
    // return true if it holds a single integer, otherwise return false
    public boolean isInteger();

    // return the single integer if it holds a single integer, otherwise return null
    public Integer getInteger();

    // return the list if it holds a list, otherwise return null
    public List<NestedInteger> getList();
}

class NestedInteger {
public:
    // return true if this NestedInteger holds a single integer, otherwise return false
    bool isInteger();

    // return the single integer that this NestedInteger
    // holds, if it holds a single integer, otherwise return
    int getInteger();

    // return the list that this NestedInteger holds, if it holds a list, otherwise return null
    vector<NestedInteger> getList();
};

class NestedInteger:
    def isInteger(self) -> bool:
        # If it stores an integer, return True, otherwise return False
        pass

    def getInteger(self) -> int:
        # If it stores an integer, return the integer, otherwise return None
        pass

    def getList(self) -> List['NestedInteger']:
        # If it stores a list, return the list, otherwise return None
        pass

type NestedInteger struct {}

// Return true if it holds a single integer, otherwise return false
func (ni NestedInteger) isInteger() bool {}

// Return the single integer if it holds a single integer, otherwise return null
func (ni NestedInteger) getInteger() int {}

// Return the list if it holds a list, otherwise return null
func (ni NestedInteger) getList() []NestedInteger {}

var NestedInteger = {
    // return true if this NestedInteger holds a single integer, otherwise return false
    isInteger: function () {},
    // return the single integer that this NestedInteger
    // holds, if it holds a single integer. Otherwise return
    getInteger: function () {},
    // return the list that this NestedInteger holds, if it holds a list. Otherwise return null
    getList: function () {}
};

我们的算法会被输入一个 NestedInteger 列表，我们需要做的就是写一个迭代器类，将这个带有嵌套结构 NestedInteger 的列表「拍平」：

public class NestedIterator implements Iterator<Integer> {
    // The constructor takes a list of NestedInteger as input
    public NestedIterator(List<NestedInteger> nestedList) {}
    
    // Return the next integer
    public Integer next() {}

    // Is there a next element?
    public boolean hasNext() {}
}

class NestedIterator: public Iterator<int> {
public:
    // Constructor takes a list of NestedInteger
    NestedIterator(vector<NestedInteger> &nestedList) {}
    
    // Return the next integer
    int next() {}

    // Does it have the next element?
    bool hasNext() {}
};

class NestedIterator:
    def __init__(self, nestedList: List[NestedInteger]):
        # The constructor takes a list of NestedInteger
        pass

    # Return the next integer
    def next(self) -> int:
        pass

    # Is there a next element?
    def hasNext(self) -> bool:
        pass

type NestedIterator struct{}

// The constructor takes a list of NestedInteger as input
func Constructor(nestedList []*NestedInteger) *NestedIterator {}

// Return the next integer
func (iter *NestedIterator) Next() int {}

// Is there a next element?
func (iter *NestedIterator) HasNext() bool {}

var NestedIterator = function(nestedList) {
    // The constructor takes a list of NestedInteger as input
}

// Return the next integer
NestedIterator.prototype.next = function() {}

// Is there a next element?
NestedIterator.prototype.hasNext = function() {}

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

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

Here are several examples given in the problem:

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By repeatedly calling next until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By repeatedly calling next until hasNext returns false, the order of elements returned by next should be: [1,4,6].

For example, in Example 1, the input list contains three NestedInteger objects: two list-type NestedInteger objects and one integer-type NestedInteger object.

Those who have studied design patterns may know that the iterator is also a design pattern. Its purpose is to hide the details of the underlying data structure from the caller, allowing them to traverse the data simply using the hasNext and next methods in an orderly manner.

Why is this problem so enlightening? Recently, I've been using a software similar to Evernote called Notion (quite famous). One highlight of this software is the concept that "everything is a block." For instance, headings, pages, and tables are all blocks. Some blocks can even be nested infinitely, breaking the traditional notebook structure of "folder" -> "notebook" -> "note."

Reflecting on this algorithm problem, the NestedInteger structure is actually a type that supports infinite nesting and can represent both integers and lists. I think the core data structure of Notion, the block, is likely designed with a similar approach.

So, getting back to the algorithm problem, how do we solve it? The NestedInteger structure can be infinitely nested. How do we "flatten" this structure to hide the underlying details for the iterator's caller and obtain a flattened output?

II. Solution Approach