364. Nested List Weight Sum II

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; 13 + 42 + 6*1 = 17)

先计算depth, 再计算

这是一种比较直接的做法，就是先计算出最深的depth. 然后，每一层深度递减.

int sum = 0;
public int depthSumInverse(List<NestedInteger> nestedList) {
    if (nestedList == null)
        return 0;
    int depth = maxDepth(nestedList);
    helper(nestedList, depth);
    return sum;
}
public int maxDepth(List<NestedInteger> nestedList) {
    int depth = 0;
    for (NestedInteger n : nestedList) {
        if (!n.isInteger()) {
            depth = Math.max(maxDepth(n.getList()), depth);
        }
    }
    return depth + 1;
}
public void helper(List<NestedInteger> nestedList, int depth) {
    for (NestedInteger n : nestedList) {
        if (n.isInteger()) {
            sum += n.getInteger() * depth;
        } else {
            helper(n.getList(), depth - 1);
        }
    }
}

BFS

开始也想这样做来着，但是没有处理好depth. 譬如说 [1,[4,[6]]]，这样的话，先访问的是1，但是它的深度应该是3，而不是1。但是这个方法里很好的处理了这个问题。就是把没有乘以depth的值，每向下一层，就多加到total里一次。

public int depthSumInverse(List<NestedInteger> nestedList) {
    if (nestedList == null) return 0;
    Queue<NestedInteger> queue = new LinkedList<NestedInteger>();
    int prev = 0;
    int total = 0;
    for (NestedInteger next : nestedList) {
        queue.offer(next);
    }
    while (!queue.isEmpty()) {
        int size = queue.size();
        int levelSum = 0;
        for (int i = 0; i < size; i++) {
            NestedInteger current = queue.poll();
            if (current.isInteger()) levelSum += current.getInteger();
            List<NestedInteger> nextList = current.getList();
            if (nextList != null) {
                for (NestedInteger next : nextList) {
                    queue.offer(next);
                }
            }
        }
        prev += levelSum;
        total += prev;
    }
    return total;
}

跟上一种很像，也算是BFS

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

Ref: