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;
}
JAVA AC BFS solution


@dianhua1560 No, I think we do need it. The beauty of this solution is to have levelSum and pre which acts as depth variable to make sure every NestedInteger has the right depth.

@steve.j.sun Nope we dont... if we just add up the values to pre we still get the same answer.

@steve.j.sun No we don't need.
What @dianhua1560 is trying to say is using
prev
in place oflevelSum
 updatingprev
with current level elements, and adding it tototal
at each level, allowing the previous elements to be added repeatedly at each level.while (!queue.isEmpty()) { int size = queue.size(); // int levelSum = 0; for (int i = 0; i < size; i++) { NestedInteger current = queue.poll(); if (current.isInteger()) prev += current.getInteger(); // < prev is not reset to 0 List<NestedInteger> nextList = current.getList(); if (nextList != null) { for (NestedInteger next: nextList) { queue.offer(next); } } } //prev += levelSum; total += prev; }

The logic could be improved for better readability in handling whether it's an integer or a list
public int depthSumInverse(List<NestedInteger> nestedList) { int prevSum = 0, totalSum = 0; Deque<NestedInteger> queue = new ArrayDeque(); for (NestedInteger ni : nestedList) { queue.offerLast(ni); } while (!queue.isEmpty()) { int size = queue.size(), levelSum = 0; for (int i = 0; i < size; i++) { NestedInteger current = queue.pollFirst(); if (current.isInteger()) { levelSum += current.getInteger(); } else { for (NestedInteger ni: current.getList()) { queue.offerLast(ni); } } } prevSum += levelSum; totalSum += prevSum; } return totalSum; }

Thank you for the code. Here is my python solution:
class Solution(object): def depthSumInverse(self, nestedList): """ :type nestedList: List[NestedInteger] :rtype: int """ # solution 2 queue if not nestedList: return 0 queue = collections.deque(nestedList) pre = 0 res = 0 while queue: n = len(queue) tempsum = 0 for i in range(n): cur = queue.popleft() if cur.isInteger(): tempsum += cur.getInteger() for list in cur.getList(): queue.append(list) pre += tempsum res += pre return res