Java easy to understand solution


  • 0
    D
    /**
     * // This is the interface that allows for creating nested lists.
     * // You should not implement it, or speculate about its implementation
     * public interface NestedInteger {
     *
     *     // @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();
     *
     *     // @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();
     * }
     */
    public class Solution {
        Map<Integer, Integer> map = new HashMap<>();
        
        public int depthSumInverse(List<NestedInteger> nestedList) {
            int ret = 0;
            
            //use dfs to travese the List and put (depth, number) to the map
            dfs(nestedList, 1);
            
            int maxDepth = Integer.MIN_VALUE;
            
            //get the max depth
            for (int n : map.keySet()) {
                if (n>maxDepth)
                    maxDepth = n;
            }
            
            //get the sum
            for (int n : map.keySet()) {
                ret += (maxDepth-n+1)*map.get(n);
            }
            
            return ret;
        }
        
        void dfs(List<NestedInteger> nestedList, int depth) {
            
            for (NestedInteger item : nestedList) {
                if (item.isInteger()) {
                    Integer num = map.get(depth);
                    if (num == null) {
                        map.put(depth, item.getInteger());
                    }
                    else {
                        map.put(depth, map.get(depth) + item.getInteger());
                    }
                }
                else {
                    dfs(item.getList(), depth+1);
                }
            }
        }
    }

Log in to reply
 

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