1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int depthSum(List<NestedInteger> nestedList) {
int ans = 0;
for (NestedInteger e : nestedList) {
ans += helper(e, 1);
}
return ans;
}
private int helper(NestedInteger nested, int depth) {
int ans = 0;
if (nested.isInteger()) {
ans += nested.getInteger() * depth;
} else {
List<NestedInteger> list = nested.getList();
for (NestedInteger e : list) {
ans += helper(e, depth + 1);
}
}
return ans;
}
}
|
DFS去做. 递归函数的功能就是给一个NestedInteger以及它的depth, 它能告诉我们这个NestedInteger展开是多少. 比如[[1, 2, 3], 3] 里面的[1, 2, 3]的depth是2, 外面的3depth是1, 我们为了求外面的list的值, 就需要知道里面list的值以及3的值. 因此自然而然联想到了用递归函数来解决.
时间复杂度: O(n) n是数字的个数.
空间复杂度: O(H) h是深度.
