JAVA AC BFS solution


  • 35
    J
    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;
        }

  • 4
    D

    Great solution. We don't actually need the levelSum variable. We can just update the prev at each level and add it to total.


  • 0
    S

    @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.


  • 0
    S

    Elegant! Upvoted!


  • 1
    D

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


  • 2

    @steve.j.sun No we don't need.

    What @dianhua1560 is trying to say is using prev in place of levelSum - updating prev with current level elements, and adding it to total 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;
        }

  • 0

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

Log in to reply
 

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