> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/binary_tree/nestedinteger_lei.md).

# NestedInteger 类

## NestedInteger 类

#### 所有的 NestedInteger 问题，都是多叉树的问题。

#### 这树，长这样：

![](/files/-MUt7ajPSN_Gr74ovRtX)

### (G) [Flatten List](http://www.lintcode.com/en/problem/flatten-list/)

递归的很简单，对于每棵 tree root 都是一个 【左 - 右】 的顺序 dfs 处理其 subtrees.

```java
    public List<Integer> flatten(List<NestedInteger> nestedList) {
        // Write your code here
        List<Integer> rst = new ArrayList<>();
        for(NestedInteger node : nestedList){
            dfs(rst, node);
        }
        return rst;
    }

    private void dfs(List<Integer> rst, NestedInteger node){
        if(node.isInteger()){
            rst.add(node.getInteger());
        } else {
            for(NestedInteger next : node.getList()){
                dfs(rst, next);
            }
        }
    }
```

#### 迭代先试了下 BFS ，发现顺序有问题。靠 Stack 遇到 List 就反向遍历 push 倒是能跑通。

#### 这个迭代写法其实就是自己用 Stack 复现了一遍递归的过程。

```java
    public List<Integer> flatten(List<NestedInteger> nestedList) {
        // Write your code here
        List<Integer> rst = new ArrayList<>();
        Stack<NestedInteger> stack = new Stack<>();

        for(int i = nestedList.size() - 1; i >= 0; i--){
            stack.push(nestedList.get(i));
        }

        while(!stack.isEmpty()){
            NestedInteger node = stack.pop();
            if(node.isInteger()){
                rst.add(node.getInteger());
            } else {
                List<NestedInteger> list = node.getList();
                for(int i = list.size() - 1; i >= 0; i--){
                    stack.push(list.get(i));
                }
            }
        }
        return rst;
    }
```

### [Nested List Weight Sum](https://leetcode.com/problems/nested-list-weight-sum/)

就是最简单的 DFS，非常 trivial 的问题。。

```java
public class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        int sum = 0;
        for(NestedInteger num : nestedList){
            sum += dfs(num, 1);
        }
        return sum;
    }

    private int dfs(NestedInteger nestedInt, int depth){
        if(nestedInt.isInteger()){
            return depth * nestedInt.getInteger();
        } else {
            int sum = 0;
            List<NestedInteger> list = nestedInt.getList();
            for(NestedInteger num : list){
                sum += dfs(num, depth + 1);
            }
            return sum;
        }
    }
}
```

### [Nested List Weight Sum II](https://leetcode.com/problems/nested-list-weight-sum-ii/)

从上往下递归可以传参数，自底向上递归传 tuple.

比较诡异的是 \[\[-1], \[\[-1]]] 这样的 test case ，第一个 \[-1] 的 weight 居然是 2，导致最终结果是 -3 .. 让我觉得这题的 test case 定义有点不清楚。。

于是下面这个 dfs 的代码会出错，因为没正确处理当前 list 也是嵌套的正确 weight. 这段代码的思路是对于每一个位置，其 weight = 其子树的最深距离，但是和原题的定义不一样。

#### 这题的正确理解是，每当看到 Integer，代表这是一个leaf node； 每当看到一个 List，代表这是一个 subtree.

```java
public class Solution {
    private class Tuple{
        int sum;
        int depth;
        public Tuple(int val, int dep){
            sum = val;
            depth = dep;
        }
    }
    public int depthSumInverse(List<NestedInteger> nestedList) {
        return dfs(nestedList).sum;
    }

    private Tuple dfs(List<NestedInteger> list){
        int sum = 0;
        int maxDepth = 1;
        for(NestedInteger node : list){
            if(!node.isInteger()){
                Tuple tuple = dfs(node.getList());
                sum += tuple.sum;
                maxDepth = Math.max(maxDepth, tuple.depth + 1);
            }
        }
        for(NestedInteger node : list){
            if(node.isInteger()) sum += maxDepth * node.getInteger();
        }

        return new Tuple(sum, maxDepth);
    }
}
```

于是乎这题的正确打开姿势其实是，自顶向下 level order 的看，只要下面还有一层，就把当前的所有结果都再加上一遍，起到相乘的效果；这样随着探索的不断深入，就可以正确地得到每层的正确 weight 了，因为每个 node 的 weight = 这个 node 到树最深节点的距离，一个天然的 BFS 问题。

```java
public class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        int total = 0, prevAll = 0;
        while(!nestedList.isEmpty()){
            List<NestedInteger> nextLvl = new ArrayList<NestedInteger>();
            for(NestedInteger next : nestedList){
                if(next.isInteger()){
                    prevAll += next.getInteger();
                } else {
                    nextLvl.addAll(next.getList());
                }
            }

            total += prevAll;
            nestedList = nextLvl;
        }

        return total;
    }
}
```

这题当然也有 DFS 解法，要先把图过一遍，侦查好 maxDepth; 然后递归解决的时候，每一层的权重是 maxDepth - curDepth;

居然能一次 AC ，好神奇。。

```java
public class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        int maxDepth = 0;
        for(NestedInteger next : nestedList){
            maxDepth = Math.max(getMaxDepth(next), maxDepth);
        }

        int sum = 0;
        for(NestedInteger next : nestedList){
            sum += dfs(next, maxDepth, 0);
        }

        return sum;
    }

    private int dfs(NestedInteger node, int maxDepth, int curDepth){
        if(node.isInteger()){
            return node.getInteger() * (maxDepth - curDepth);
        } else {
            int sum = 0;
            for(NestedInteger next : node.getList()){
                sum += dfs(next, maxDepth, curDepth + 1);
            }
            return sum;
        }
    }

    private int getMaxDepth(NestedInteger num){
        if(num.isInteger()) return 1;

        int max = 0;
        List<NestedInteger> nestedList = num.getList();
        for(NestedInteger next : nestedList){
            max = Math.max(getMaxDepth(next), max);
        }

        return max + 1;
    }
}
```

### [Flatten Nested List Iterator](https://leetcode.com/problems/flatten-nested-list-iterator/)

这题和 BST iterator 很像，因为实际上都是利用 stack + cur 指针做一个 inorder 遍历。

不同之处是，Binary Tree 是双叉的，有个 node 就可以满足输出当前元素 + 寻找下一元素的需要，我们这个情况要复杂一些。

#### NestedInteger 是一种树状结构，其中每一个是 List 的元素代表一个三角形，下面有自己的子树。

![](/files/-MUt7ajQNdRzJfJ-EJNq)

了解了这个结构之后，为了遍历寻找下一个元素，就需要依靠 List 作为一个 Collection interface 里自带的 iterator 了，在这里 iterator 就充当了 BST 里面 cur 指针的地位，用于在树上定位，和寻找下一个元素； 同时 Stack<> 所存储的，就是各个 iterator.

实现过程中要注意的是，test case 会根据 boolean hasNext 决定是否继续输出，而这种结构不同于 binary tree，可能会有 \[ \[ ] ] 这种情况，此时 stack 里有东西，cur.hasNext() 也返回 true，无法正确得知下面是否真的有元素存在。

所以要在 hasNext 里面执行程序逻辑。

同时对于一个 iterator，如果已经没有新元素了也不必要 push 到 stack 中。

#### 速度超过 80.50% ，下面的代码能 AC

## 但是我觉得不算很严谨，如果测试用例调用很多次 hasNext()，会对现有的 iterator 造成影响，不应该是正确的。

```java
public class NestedIterator implements Iterator<Integer> {
    Stack<Iterator<NestedInteger>> stack;
    Iterator<NestedInteger> cur;
    Integer next;

    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<Iterator<NestedInteger>>();
        cur = nestedList.iterator();
        next = null;
    }

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

    @Override
    public boolean hasNext() {
        while(cur.hasNext() || !stack.isEmpty()){
            while(cur.hasNext()){
                NestedInteger elem = cur.next();
                if(elem.isInteger()) {
                    next = elem.getInteger();
                    return true;
                } else {
                    if(cur.hasNext()) stack.push(cur);
                    cur = elem.getList().iterator();
                }
            }
            if(!stack.isEmpty()) cur = stack.pop();
        }

        return false;
    }
}
```

#### 我比较认同的写法是这种，用内部函数来准备 next() 和 hasNext() API 的返回。

```java
public class NestedIterator implements Iterator<Integer> {

    Stack<Iterator<NestedInteger>> stack;
    Iterator<NestedInteger> cur;
    Integer num;

    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        cur = nestedList.iterator();
        num = internalNext();
    }

    private Integer internalNext(){
        if(cur.hasNext()){
            NestedInteger elem = cur.next();
            if(elem.isInteger()){
                return elem.getInteger();
            } else {
                if(cur.hasNext()) stack.push(cur);
                cur = elem.getList().iterator();
                return internalNext();
            }
        } else {
            if(stack.isEmpty()) return null;
            cur = stack.pop();
            return internalNext();
        }
    }

    @Override
    public Integer next() {
        Integer tmp = num;
        num = internalNext();
        return tmp;
    }

    @Override
    public boolean hasNext() {
        return (num != null);
    }
}
```

#### 中间的部分改成迭代也很简单，这样就行；

```java
    private Integer internalNext(){
        while(!stack.isEmpty() || cur.hasNext()){
            if(cur.hasNext()){
                NestedInteger elem = cur.next();
                if(elem.isInteger()){
                    return elem.getInteger();
                } else {
                    if(cur.hasNext()) stack.push(cur);
                    cur = elem.getList().iterator();
                    continue;
                }
            } else {
                if(stack.isEmpty()) return null;
                cur = stack.pop();
                continue;
            }
        }
        return null;
    }
```