关于算法:题目不让我干什么我偏要干什么

读完本文，你能够去力扣拿下如下题目：

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();}

PS：我认真写了 100 多篇原创，手把手刷 200 道力扣题目，全副公布在 labuladong 的算法小抄，继续更新 。倡议珍藏， 依照我的文章程序刷题，把握各种算法套路后投再入题海就蛟龙得水了。

咱们的算法会被输出一个 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 这个构造，也不应该去猜想它的实现？为什么？凭什么？是不是题目在误导我？是不是我进行揣测之后，这道题就不攻自破 了？

你看，labuladong 可不是什么好孩子，你不让揣测，我就偏偏要去揣测！我反手就把 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 的第一个元素是列表类型，则一直开展这个元素，直到第一个元素是整数类型。

因为调用 next 办法之前肯定会调用 hasNext 办法，这就能够保障每次调用 next 办法的时候第一个元素是整数型，间接返回并删除第一个元素即可。

看一下代码：

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();}
}

以这种办法，合乎迭代器惰性求值的个性，是比拟好的解法。