讀完本文，你可以去力扣拿下如下題目：

733.扁平化巢狀列表

-----------

今天來講一道非常有啟發性的設計題目，為什麼說它有啟發性，我們後面再說。

一、題目描述

這是 LeetCode 第 341.扁平化巢狀列表迭代器，我來描述一下題目：

首先，現在有一種資料結構 NestedInteger，這個結構中存的資料可能是一個 Integer 整數，也可能是一個 NestedInteger 列表。注意，這個列表裡面裝著的是 NestedInteger，也就是說這個列表中的每一個元素可能是個整數，可能又是個列表，這樣無限遞迴巢狀下去……

NestedInteger 有如下 API：

public class NestedInteger {    // 如果其中存的是一個整數，則返回 true，否則返回 false    public boolean isInteger();    // 如果其中存的是一個整數，則返回這個整數，否則返回 null    public Integer getInteger();    // 如果其中存的是一個列表，則返回這個列表，否則返回 null    public List<NestedInteger> getList();}

我們的演算法會被輸入一個 NestedInteger 列表，我們需要做的就是寫一個迭代器類，將這個帶有巢狀結構 NestedInteger 的列表「拍平」：

public class NestedIterator implements Iterator<Integer> {    // 構造器輸入一個 NestedInteger 列表    public NestedIterator(List<NestedInteger> nestedList) {}        // 返回下一個整數    public Integer next() {}    // 是否還有下一個元素？    public boolean hasNext() {}}

我們寫的這個類會被這樣呼叫，先呼叫 hasNext 方法，後呼叫 next 方法：

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

比如示例 1，輸入的列表裡有三個 NestedInteger，兩個列表型的 NestedInteger 和一個整數型的 NestedInteger。

學過設計模式的朋友應該知道，迭代器也是設計模式的一種，目的就是為呼叫者遮蔽底層資料結構的細節，簡單地透過 hasNext 和 next 方法有序地進行遍歷。

為什麼說這個題目很有啟發性呢？因為我最近在用一款類似印象筆記的軟體，叫做 Notion（挺有名的）。這個軟體的一個亮點就是「萬物皆 block」，比如說標題、頁面、表格都是 block。有的 block 甚至可以無限巢狀，這就打破了傳統筆記本「資料夾」->「筆記本」->「筆記」的三層結構。

回想這個演算法問題，NestedInteger 結構實際上也是一種支援無限巢狀的結構，而且可以同時表示整數和列表兩種不同型別，我想 Notion 的核心資料結構 block 估計也是這樣的一種設計思路。

那麼話說回來，對於這個演算法問題，我們怎麼解決呢？NestedInteger 結構可以無限巢狀，怎麼把這個結構「打平」，為迭代器的呼叫者遮蔽底層細節，得到扁平化的輸出呢？

二、解題思路

顯然，NestedInteger 這個神奇的資料結構是問題的關鍵，不過題目專門提醒我們：

You should not implement it, or speculate about its implementation.

我不應該去嘗試實現 NestedInteger 這個結構，也不應該去猜測它的實現？為什麼？憑什麼？是不是題目在誤導我？是不是我進行推測之後，這道題就不攻自破了？

public class NestedInteger {    private Integer val;    private List<NestedInteger> list;    public NestedInteger(Integer val) {        this.val = val;        this.list = null;    }    public NestedInteger(List<NestedInteger> list) {        this.list = list;        this.val = null;    }​    // 如果其中存的是一個整數，則返回 true，否則返回 false    public boolean isInteger() {        return val != null;    }​    // 如果其中存的是一個整數，則返回這個整數，否則返回 null    public Integer getInteger() {        return this.val;    }​    // 如果其中存的是一個列表，則返回這個列表，否則返回 null    public List<NestedInteger> getList() {        return this.list;    }}

嗯，其實這個實現也不難嘛，寫出來之後，我不禁翻出前文 學習資料結構和演算法的框架思維，發現這玩意兒竟然……

class NestedInteger {    Integer val;    List<NestedInteger> list;}​/* 基本的 N 叉樹節點 */class TreeNode {    int val;    TreeNode[] children;}

這玩意兒不就是棵 N 叉樹嗎？葉子節點是 Integer 型別，其 val 欄位非空；其他節點都是 List<NestedInteger> 型別，其 val 欄位為空，但是 list 欄位非空，裝著孩子節點。

比如說輸入是 [[1,1],2,[1,1]]，其實就是如下樹狀結構：

好的，剛才題目說什麼來著？把一個 NestedInteger 扁平化對吧？這不就等價於遍歷一棵 N 叉樹的所有「葉子節點」嗎？我把所有葉子節點都拿出來，不就可以作為迭代器進行遍歷了嗎？

N 叉樹的遍歷怎麼整？我又不禁翻出前文 學習資料結構和演算法的框架思維 找出框架：

void traverse(TreeNode root) {    for (TreeNode child : root.children)        traverse(child);

這個框架可以遍歷所有節點，而我們只對整數型的 NestedInteger 感興趣，也就是我們只想要「葉子節點」，所以 traverse 函式只要在到達葉子節點的時候把 val 加入結果列表即可：

class NestedIterator implements Iterator<Integer> {​    private Iterator<Integer> it;        public NestedIterator(List<NestedInteger> nestedList) {        // 存放將 nestedList 打平的結果        List<Integer> result = new LinkedList<>();        for (NestedInteger node : nestedList) {            // 以每個節點為根遍歷            traverse(node, result);        }        // 得到 result 列表的迭代器        this.it = result.iterator();    }​    public Integer next() {        return it.next();    }​    public boolean hasNext() {        return it.hasNext();    }            // 遍歷以 root 為根的多叉樹，將葉子節點的值加入 result 列表    private void traverse(NestedInteger root, List<Integer> result) {        if (root.isInteger()) {            // 到達葉子節點            result.add(root.getInteger());            return;        }        // 遍歷框架        for (NestedInteger child : root.getList()) {            traverse(child, result);        }    }}

這樣，我們就把原問題巧妙轉化成了一個 N 叉樹的遍歷問題，並且得到了解法。

三、進階思路

以上解法雖然可以透過，但是在面試中，也許是有瑕疵的。

我們的解法中，一次性算出了所有葉子節點的值，全部裝到 result 列表，也就是記憶體中，next 和 hasNext 方法只是在對 result 列表做迭代。如果輸入的規模非常大，建構函式中的計算就會很慢，而且很佔用記憶體。

一般的迭代器求值應該是「惰性的」，也就是說，如果你要一個結果，我就算一個（或是一小部分）結果出來，而不是一次把所有結果都算出來。

如果想做到這一點，使用遞迴函式進行 DFS 遍歷肯定是不行的，而且我們其實只關心「葉子節點」，所以傳統的 BFS 演算法也不行。實際的思路很簡單：

呼叫 hasNext 時，如果 nestedList 的第一個元素是列表型別，則不斷展開這個元素，直到第一個元素是整數型別。

看一下程式碼：

public class NestedIterator implements Iterator<Integer> {    private LinkedList<NestedInteger> list;    public NestedIterator(List<NestedInteger> nestedList) {        // 不直接用 nestedList 的引用，是因為不能確定它的底層實現        // 必須保證是 LinkedList，否則下面的 addFirst 會很低效        list = new LinkedList<>(nestedList);    }    public Integer next() {        // hasNext 方法保證了第一個元素一定是整數型別        return list.remove(0).getInteger();    }    public boolean hasNext() {        // 迴圈拆分列表元素，直到列表第一個元素是整數型別        while (!list.isEmpty() && !list.get(0).isInteger()) {            // 當列表開頭第一個元素是列表型別時，進入迴圈            List<NestedInteger> first = list.remove(0).getList();            // 將第一個列表打平並按順序新增到開頭            for (int i = first.size() - 1; i >= 0; i--) {                list.addFirst(first.get(i));            }        }        return !list.isEmpty();    }}

以這種方法，符合迭代器惰性求值的特性，是比較好的解法。