Java "get max depth first" 2-pass approach. BTW Is empty list possible ?


  • 0

    The trivial idea is do a DFS to get the max depth and then pass it to another helper method to the sum, very similar to nested list sum I. However, it is not easy to find the max depth if empty List is allowed.

    public class Solution {
        public int depthSumInverse(List<NestedInteger> nestedList) {
            int weight = maxDepth(nestedList);
            return depthSumInverseHelper(nestedList, weight);
        }
    
        
        private int depthSumInverseHelper(List<NestedInteger> nestedList, int weight) {
            int sum = 0;
            for (NestedInteger child : nestedList) {
                sum += child.isInteger() ? weight * child.getInteger() : depthSumInverseHelper(child.getList(), weight - 1);
            }
            return sum;
        }
        
        private int maxDepth(List<NestedInteger> nestedList) {
            int max = 0;
            for (NestedInteger child : nestedList) {
                if (!child.isInteger()) {
                    max = Math.max(max, maxDepth(child.getList()));
                }    
            }
            return max + 1;
        }
    }

  • 0
    F

    I don't know if he's got any test case with empty list, but I took that into my consideration.


Log in to reply
 

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