Problem

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:
Given the list[[1,1],2,[1,1]], return 8. (four 1's at depth 1, one 2 at depth 2)

Example 2:
Given the list[1,[4,[6]]], return 17. (one 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17)

思路一（bfs）

• 因为要计算每一层的和以及得到该层的深度， 我们可以用bfs来遍历每一层， 用list来记录每一层的和，然后list.size 就是最大深度。
• 通过list.size() - i可以得到每一层的深度

    public int depthSumInverse(List<NestedInteger> nestedList) {
        if (nestedList == null || nestedList.size() == 0) return 0;
        Queue<NestedInteger> queue = new LinkedList<>();
        for (NestedInteger ni: nestedList) queue.offer(ni);

        List<Integer> res = new ArrayList<>();
        int depth = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            if (res.size() < depth + 1) res.add(0);
            for (int i = 0; i < size; i++) {
                NestedInteger curt = queue.poll();
                if (curt.isInteger()) res.set(depth, res.get(depth) + curt.getInteger());
                else {
                    for (NestedInteger next: curt.getList()) {
                        queue.offer(next);
                    }
                }
            }
            depth++;
        }
        int ans = 0;
        for (int i = 0;i < res.size(); i++) {
            ans += res.get(i) * (res.size() - i);
        }
        return ans;
    }

思路二（dfs）

• dfs拿着一个list，自上而下遍历，使用bfs相同的思路填充数组。 最后通过遍历这个list得到结果
• 思路就是逐渐消耗nestedList里面的个数， 就如 Shopping offer 里面的需求

写法一

    public int depthSumInverse(List<NestedInteger> nestedList) {
        if (nestedList == null || nestedList.size() == 0) return 0;
        List<Integer> res = new ArrayList<>();
        for (NestedInteger ni: nestedList)
            dfs (ni, 0, res);
        int ans = 0;
        for (int i = 0; i < res.size(); i++) {
            ans += res.get(i) * (res.size() - i);
        }
        return ans;
    }

    private void dfs (NestedInteger ni, int depth, List<Integer> res) {
        if (res.size() < depth + 1) res.add(0);

        if (ni.isInteger()) {
            res.set(depth, res.get(depth) + ni.getInteger());
        } else {
            for (NestedInteger next: ni.getList())
                dfs(next, depth + 1, res);
        }
    }

写法二

    public int depthSumInverse(List<NestedInteger> nestedList) {
        if (nestedList == null || nestedList.size() == 0) return 0;
        List<Integer> res = new ArrayList<>();
        dfs (nestedList, 0, res);
        int ans = 0;
        for (int i = 0; i < res.size(); i++) {
            ans += res.get(i) * (res.size() - i);
        }
        return ans;
    }

    private void dfs (List<NestedInteger> list, int depth, List<Integer> res) {
        if (list.size() == 0) return;
        if (res.size() < depth + 1) res.add(0);

        List<NestedInteger> nextLayer = new ArrayList<>();

        for (NestedInteger ni: list) {
            if (ni.isInteger()) {
                res.set(depth, res.get(depth) + ni.getInteger());
            } else {
                nextLayer.addAll(ni.getList());
            }
        }
        dfs(nextLayer, depth + 1, res);
    }