# 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;
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/binary_tree/nestedinteger_lei.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.