[LeetCode 364] Nested List Weigh

Solution

1. 先求出Depth
2. 再把Depth递减求值

/**
 * // 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) {
        if (nestedList == null || nestedList.size () == 0)
            return 0;
        
        // 1, get depth
        int depth = getDepth (nestedList);
        
        //2. calculate the result
        return depthSumInverseHelper (nestedList, depth);
    }
    
    public int getDepth (List<NestedInteger> nestedList) {
        int depth = 0;
        
        for (NestedInteger nested : nestedList) {
            if (nested.isInteger ()) {
                depth = Math.max (depth, 1);
            } else {
                depth = Math.max (depth, getDepth (nested.getList ()) + 1);
            }
        }
        
        return depth;
    }
    
    public int depthSumInverseHelper (List<NestedInteger> nestedList, int currentDepth) {
        int sum = 0;
        
        for (NestedInteger nested : nestedList) {
            if (nested.isInteger ()) {
                sum += currentDepth * nested.getInteger ();
            } else {
                sum += depthSumInverseHelper (nested.getList (), currentDepth - 1);
            }
        }
        
        return sum;
    }
}