Leetcode/Linkedin -- 339.364. Nested List Weight Sum I/II(DFS)

339.364. Nested List Weight Sum II(DFS)
https://leetcode.com/problems/nested-list-weight-sum/

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

I is top down

Example 1:
Given the list [[1,1],2,[1,1]], return 10. (four 1's at depth 2, one 2 at depth 1)

Example 2:
Given the list [1,[4,[6]]], return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27)‘’

public class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        return helper(nestedList, 1);
    }
    int helper(List<NestedInteger> nestedList,int depth){
        if(nestedList == null)return 0;
        int res = 0;
        for(NestedInteger e:nestedList){ 
            if(e.isInteger()) 
                res += e.getInteger()*depth;//add num in cur list
            else 
                res += helper(e.getList(), depth+1);//add result of element list in cur list
        }
        return  res;
    }
}

II is bottom up

Example 1:
Given the list [[1,1],2,[1,1]], return 8. (four 1's at depth 1, one 2 at depth 2)

Example 2:
Given the list [1,[4,[6]]], return 17. (one 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17)

思路： dfs, when meeting single number, add it to result. Else keep travelling and modify depth. 

Complexity: Time O(n) n integer. Space: O(k) for recursion stack where k is the max level of depth.

public class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        int depth = getDepth(nestedList);
        return helper(nestedList, depth);//topdown: depth is 1, add up 
    }
    int getDepth(List<NestedInteger> nestedList){
        if(nestedList == null)return 0;
        int h = 1;
        for(NestedInteger e:nestedList){ 
            if(e.isInteger())continue;
            else h =Math.max(h, 1+getDepth(e.getList()));//key is to track the deepest depth
        }
        return h;
    }
    int helper(List<NestedInteger> nestedList,int depth){
        if(nestedList == null)return 0;
        int res = 0;
        for(NestedInteger e:nestedList){ 
            if(e.isInteger()) 
                res += e.getInteger()*depth;
            else 
                res += helper(e.getList(),depth-1);//top down will be +1
        }
        return  res;
    }
}