339. Nested List Weight Sum

Problem description:

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.

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 + 42 + 63 = 27)

Solution DFS:

Traverse the entire array,

• if it’s integer, add to result
• if it’s a list, go to next layer

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        
        def dfs(nestedNode, level):
            res = 0
            for node in nestedNode:
                if node.isInteger():
                    res += node.getInteger()*level
                else:
                    res += dfs(node.getList(), level+1)
            return res
        
        return dfs(nestedList, 1)

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Constructor initializes an empty nested list.
 *     NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     NestedInteger(int value);
 *
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Set this NestedInteger to hold a single integer.
 *     void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     void add(const NestedInteger &ni);
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return dfs(nestedList, 1);
    }
    
    int dfs(vector<NestedInteger>& nestedList, int depth){
        int res= 0;
        
        for(int i= 0; i< nestedList.size(); i++){
            if(nestedList[i].isInteger())
                res+= (nestedList[i].getInteger()*depth);
            else
                res+= dfs(nestedList[i].getList(), depth+1);
        }
        return res;
    }
};

Solution BFS

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        if len(nestedList) == 0: return 0
        stack = []
        res = 0
        for n in nestedList:
            stack.append((n, 1))
        while stack:
            next, d = stack.pop(0)
            if next.isInteger():
                res += d * next.getInteger()
            else:
                for i in next.getList():
                    stack.append((i,d+1))
        return res