One pass java using a list + dfs


  • 3

    Simple one pass dfs solution. Store the values per level in a list, then traverse the result list backwards and multiply by the level number.

    public class Solution {
        public int depthSumInverse(List<NestedInteger> nestedList) {
            List<Integer> result = dfs(nestedList, 0, new ArrayList<>());
            
            int total = 0;
            for (int index = result.size() - 1; index >= 0; index--) {
                total += result.get(index) * (result.size() - index);
            }
            
            return total;
        }
        
        List<Integer> dfs(Iterable<NestedInteger> list, int depth, List<Integer> result) {
            if (depth == result.size()) {
                result.add(0);
            }
            
            for (NestedInteger integer : list) {
                if (integer.isInteger()) {
                    result.set(depth, result.get(depth) + integer.getInteger());
                } else {
                    dfs(integer.getList(), depth + 1, result);
                }
            }
            
            return result;
        }
    }

  • 0
    K

    A Stack is better maybe.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.