nested-list-weight-sum

Nested List Weight Sum – LeetCode 339

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.

Answer

Original

Code

class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return helper(nestedList, 1);
    }
    int helper(vector<NestedInteger>& nl, int depth) {
        int res = 0;
        for (auto a : nl) {
            res += a.isInteger() ? a.getInteger() * depth : helper(a.getList(), depth + 1);
        }
        return res;
    }
};

思路

简单DFS依次求值，时间复杂度$O(n)$，空间复杂度$O(n)$。

Better

思路

还没看到更好的思路。