364. Nested List Weight Sum II

Version #1 BFS

一刷

39.18 %
public class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        if (nestedList == null || nestedList.size() == 0) return 0;
        int targetSum = 0;
        Queue<NestedInteger> que = new LinkedList<>();
        for (NestedInteger ni : nestedList) {
            que.offer(ni);
        }
        int integerSum = 0;
        NestedInteger curr;
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                curr = que.poll();
                if (curr.isInteger()) {
                    integerSum += curr.getInteger();
                } else {
                    List<NestedInteger> children = curr.getList();
                    for (NestedInteger child : children) {
                        que.offer(child);
                    }
                }
            }
            targetSum += integerSum;
        }
        return targetSum;
    }
}

二刷

class Solution {

    public int depthSumInverse(List<NestedInteger> nestedList) {

        // 1 (layerSum) 

        // 1 (prevSum) 4(layerSum)

        // 1 4 6

        Queue<NestedInteger> que = new LinkedList<>();

        for (NestedInteger ni : nestedList) {

            que.offer(ni);

        }

        int prevSum = 0, sum = 0;

        while (!que.isEmpty()) {

            int size = que.size();

            int layerSum = 0;

            while (size-- > 0) {

                NestedInteger curr = que.poll();

                if (curr.isInteger()) {

                    layerSum += curr.getInteger();

                    continue;

                } 

                for (NestedInteger ni : curr.getList()) {

                    que.offer(ni);

                }

            }

            prevSum += layerSum;

            sum += prevSum;

        }

        return sum;

    }

}