Java standard BFS rewriting StefanPochmann's with extra interpretation


  • 0

    standard bfs using one queue. The queue contains only Lists of NestedInteger.
    The trick is "never reset unweighted for each level". Say, for input with 3 levels, the weight of int on the first level will be added 3 times to weighted because unweighted contains its value and is never reset.

       public class Solution {
            public int depthSumInverse(List<NestedInteger> nestedList) {
                int weighted = 0, 
                int unweighted = 0; // accumulated sum, no reset
                Queue<List<NestedInteger>> queue = new LinkedList<>();
                queue.offer(nestedList);
                while (!queue.isEmpty()) {
                    int size = queue.size();
                    for (int i = 0; i < size; i++) {//next level
                        nestedList = queue.poll();
                        for (NestedInteger ni : nestedList) {
                            if (ni.isInteger()) {
                                unweighted += ni.getInteger();
                            } else {
                                queue.offer(ni.getList());
                            }
                        }
                    }
                    weighted += unweighted;// never reset unweighted to zero
                }
                return weighted;
            }
        }

Log in to reply
 

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