Leetcode #364. Nested List Weight Sum II

[yokostan]

BFS novel solution:

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        Queue<NestedInteger> queue = new LinkedList<NestedInteger>();
        int total = 0;
        int prev = 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 curr = queue.poll();
                if (curr.isInteger()) {
                    levelSum += curr.getInteger();
                }
                List<NestedInteger> nextList = curr.getList();
                if (nextList != null) {
                    for (NestedInteger next : nextList) {
                        queue.offer(next);
                    }
                }
            }
            prev += levelSum;
            total += prev;
        }
        return total;
    }
}

Idea behind this is

a + (a+b) + (a+b+c) = 3a + 2b + c

a is integers at level 1. b is integers at level 2. c is integers at level 3.

a is levelSum a + b is prevSum + levelSum a + (a +b) is totalSum + prevSum

DFS solution:

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        int res = 0;
        int h = getHeight(nestedList);
        res = getSum(nestedList, h);
        return res;
    }

    public int getSum(List<NestedInteger> list, int h) {
        int res = 0;
        for (NestedInteger ni : list) {
            if (ni.isInteger()) {
                res += h * ni.getInteger();
            }
            else {
                List<NestedInteger> li = ni.getList();
                if (li != null) {
                    res += getSum(li, h - 1);
                }
            }
        }
        return res;
    }

    public int getHeight(List<NestedInteger> list) {
        int max = 0;
        for (NestedInteger ni : list) {
            if (ni.isInteger()) max = Math.max(1, max);
            else {
                max = Math.max(max, getHeight(ni.getList()) + 1);
            }
        }
        return max;
    }
}