364. Nested List Weight Sum II

https://leetcode.com/problems/nested-list-weight-sum-ii/description/

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 x 3 + 4 x 2 + 6 x 1 = 17)

与 339 不同的是，level 的权重相反。339 中 level 的权重是 depth，而 364 中 level 的权重是 height。只要找到 maxHeight or maxDepth 就可以了。

my solution

    public int depthSumInverse(List<NestedInteger> nestedList) {
        if (nestedList == null || nestedList.size() == 0) {
            return 0;
        }
        
        HashMap<Integer, Integer> levelSum = new HashMap<>();
        helper(nestedList, 0, levelSum);
        
        int size = levelSum.size();
        int sum = 0;
        int level = 0;
        
        while (level < size) {
            sum += (size - level) * levelSum.get(level);
            level++;
        }
        
        return sum;
    }
    
    private void helper(List<NestedInteger> nestedList, int level, HashMap<Integer, Integer> levelSum) {
        if (!levelSum.containsKey(level)) {
            levelSum.put(level, 0);
        }

        for (NestedInteger ni: nestedList) {
            if (ni.isInteger()) {
                int newSum = ni.getInteger() + levelSum.get(level);
                levelSum.put(level, newSum);
            } else {
                helper(ni.getList(), level + 1, levelSum);
            }
        }
    }

上面的 HashMap 是可以使用 ArrayList 来替代的。

BFS Solution

没写，思路跟 339 和 上面的思路基本是一致的。

Solution

from discussion
利用每一层将当前整数加起来，然后往后遍历多一层就将前面已经加过的数再加一遍

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