364. Nested List Weight Sum II

/**
 * // 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 d = depth(nestedList);
        return dfs(nestedList, d);
    }

    int depth(List<NestedInteger> list)
    {
        int res = 1;
        for(NestedInteger k : list)
        {
            if(k.isInteger()) continue;
            res = Math.max(res, 1 + depth(k.getList()));
        }
        return res;
    }

    int dfs(List<NestedInteger> list, int w)
    {
        int res = 0;
        for(NestedInteger k : list)
        {
            if(k.isInteger()) res += w * k.getInteger();
            else res += dfs(k.getList(), w - 1);
        }
        return res;
    }
}