leetcode解题: Nested List Weight Sum (339)

发表于 | 分类于

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)

解法1：Recursion with O(N) time, N is number of total elements

看到Nested，从构造上来说和递归的思路很一致。想到递归时每一次调用递归函数需要记录下当前的level。
整体的思路是对每一个element, 如果是Integer的话，当前的结果应该是数值 * level, 然后继续，如果是Nested List，那么level + 1, 然后继续递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return depthSumHelper(nestedList, 1);
    }
    int depthSumHelper(vector<NestedInteger>& nestedList, int depth) {
        int sum = 0;
        for (int i = 0; i < nestedList.size(); i++) {
            if (nestedList[i].isInteger()) {
                sum += nestedList[i].getInteger() * depth;
            } else {
                sum += depthSumHelper(nestedList[i].getList(), depth + 1);
            }
        }
        return sum;
    }
};