341. 扁平化嵌套列表迭代器

---

https://leetcode-cn.com/problems/flatten-nested-list-iterator/

• 先声明 NestedInteger 的结构（题目给出）

interface NestedInteger {

    // @return true if this NestedInteger holds a single integer, rather than a nested list.
    public boolean isInteger();

    // @return the single integer that this NestedInteger holds, if it holds a single integer
    // Return null if this NestedInteger holds a nested list
    public Integer getInteger();

    // @return the nested list that this NestedInteger holds, if it holds a nested list
    // Return null if this NestedInteger holds a single integer
    public List<NestedInteger> getList();
}

迭代器（效率最高）

• 手动遍历，将遍历结果存在集合中，然后生成迭代器，其他操作基于此迭代器即可。
• 遍历方式是DFS，因为此结构可以联系到数据结构中的 树 。

/**
 * use Java Iterator
 */
public class NestedIterator implements Iterator<Integer> {

    private Iterator<Integer> iterator;

    public NestedIterator(List<NestedInteger> nestedList) {
        List<Integer> list = new ArrayList<>();
        for (NestedInteger node : nestedList) {
            DFS(node, list);
        }
        this.iterator = list.iterator(); // all the operation use list's iterator
    }

    @Override
    public Integer next() {
        return iterator.next();
    }

    @Override
    public boolean hasNext() {
        return iterator.hasNext();
    }

    /**
     * DFS get every element into List res;
     */
    private void DFS(NestedInteger node, List<Integer> res) {
        if (node.isInteger()) {
            res.add(node.getInteger());
            return;
        }
        for (NestedInteger child : node.getList()) {
            DFS(child, res);
        }
    }

}

队列 + DFS（用队列实现 Iterator）

• 道理同上，DFS手动遍历，将遍历结果存在队列中
• 用队列手动实现 iterator 。

/**
 * use DFS and Queue
 */
public class NestedIterator implements Iterator<Integer> {

    Deque<Integer> queue = new ArrayDeque<Integer>();

    public NestedIterator(List<NestedInteger> nestedList) {
        DFS(nestedList);
    }

    @Override
    public Integer next() {
        return hasNext() ? queue.pollFirst() : -1;
    }

    @Override
    public boolean hasNext() {
        return !queue.isEmpty();
    }

    /**
     * DFS the nestedList, offer the elements into the queue
     */
    private void DFS(List<NestedInteger> nestedList) {
        for (NestedInteger elem : nestedList) {
            if (elem.isInteger()) { // elem is Integer, offer the queue
                queue.addLast(elem.getInteger());
            } else {    // elem is List, DFS the list and offer the elements into queue
                DFS(elem.getList());
            }
        }
    }

}

栈 + 递归 (Stack + Recursion)

• 不同于队列的是，队列要在初始化阶段，将遍历的结果全部处理好，最后按照顺序进行操作即可。
• 利用栈的思想是，先将这些 NestedInteger 按顺序（倒序）存放在栈中，而要使用里面的元素时，再一步步的 拆封 出来。

/**
 * use Stack and Recursion
 */
public class NestedIterator implements Iterator<Integer> {

    Deque<NestedInteger> stack = new ArrayDeque<NestedInteger>();

    public NestedIterator(List<NestedInteger> nestedList) {
        for (int i = nestedList.size() - 1; i >= 0 ; i--) {
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        return hasNext() ? stack.pop().getInteger() : -1;
    }

    @Override
    public boolean hasNext() {
        if (stack.isEmpty()) {
            return false;
        } else {    // stack not empty, judge the peek elem's type(List/Integer)
            NestedInteger elem = stack.peek();
            if (elem.isInteger()) {
                return true;
            } else { // peek elem is list, iterate the list to push elem into the stack
                elem = stack.pop();
                List<NestedInteger> list = elem.getList();
                for (int i = list.size() - 1; i >= 0; i--) {
                    stack.push(list.get(i));
                }
                return hasNext();
            }
        }
    }

}