364. Nested List Weight Sum II

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)

3/26/2018 update:
用unweighted 和weighted来做太巧了，面试的时候肯定想不出来。Use a list of int[], store integer of each level to one int[] then push to list.
[1, [4, 5, [6, 7]]]
list:      [1], [4, 5], [6, 7]
index:   0     1        2
level:    3      2       1
We can conclude from the above illustration that level = list.size - index.

Analysis:

Use BFS to add lower level val cumulatively. The idea explains itself in code. 

If we use DFS for this problem, it would be very hard to implement right. Avoid DFS when we can.

Solution:

class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        int unWeighted = 0, weighted = 0;
        if (nestedList == null) return weighted;
        while(!nestedList.isEmpty()) {
            List<NestedInteger> nextLevel = new ArrayList<>();
            for (NestedInteger n: nestedList) {
                if (n.isInteger()) {
                    unWeighted += n.getInteger();
                } else {
                    nextLevel.addAll(n.getList());
                }
            }
            weighted += unWeighted;
            nestedList = nextLevel;
        }
        return weighted;
    }
}