1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
private int[] ans;
public int[] countSubTrees(int n, int[][] edges, String labels) {
Map<Integer, List<Integer>> nodeNeighbors = new HashMap<>();
for (int[] edge : edges) {
nodeNeighbors.computeIfAbsent(edge[0], (key) -> new ArrayList<>()).add(edge[1]);
nodeNeighbors.computeIfAbsent(edge[1], (key) -> new ArrayList<>()).add(edge[0]);
}
ans = new int[n];
dfs(0, -1, labels.toCharArray(), nodeNeighbors);
return ans;
}
private int[] dfs(int currNode, int parent, char[] labels, Map<Integer, List<Integer>> nodeNeighbors) {
int[] subtreeLabelCount = new int[26];
for (int neighbor : nodeNeighbors.get(currNode)) {
if (neighbor != parent) {
mergeArray(subtreeLabelCount, dfs(neighbor, currNode, labels, nodeNeighbors));
}
}
int currNodeLabelCount = ++subtreeLabelCount[labels[currNode] - 'a'];
ans[currNode] = currNodeLabelCount;
return subtreeLabelCount;
}
private void mergeArray(int[] arr1, int[] arr2) {
for (int i = 0; i < arr1.length; i++) {
arr1[i] += arr2[i];
}
}
}
|
递归函数做的事情就是返回给定node代表的tree中各个label的count是多少. 因为label只有小写字母, 因此一个长度为26的数组即可用来表示subtree中的各个label个数的情况. 这道题理解了++, –的作用. 它是直接作用在变量上的, 也就是该变量会产生变化. 比如a++. 假如a的值之前是1, 那么a++后就变为2了.
时间复杂度: O(n)
空间复杂度: O(n)
