This approach utilizes a Depth First Search (DFS) to traverse each node of the tree. During traversal, we maintain a frequency array for each node to keep count of each label in its subtree. The recursion allows merging results from child nodes to calculate the current node's results.
The time complexity is O(n), where n is the number of nodes, because each node and edge is visited once during the DFS traversal. The space complexity is O(n), required for storing the graph representation and frequency arrays.
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5 public int[] countSubTrees(int n, int[][] edges, String labels) {
6 List<List<Integer>> graph = new ArrayList<>();
7 for (int i = 0; i < n; i++) {
8 graph.add(new ArrayList<>());
9 }
10 for (int[] edge : edges) {
11 graph.get(edge[0]).add(edge[1]);
12 graph.get(edge[1]).add(edge[0]);
13 }
14
15 int[] result = new int[n];
16 int[][] count = new int[n][26];
17 dfs(0, -1, graph, labels, count, result);
18 return result;
19 }
20
21 private void dfs(int node, int parent, List<List<Integer>> graph, String labels, int[][] count, int[] result) {
22 int labelIndex = labels.charAt(node) - 'a';
23 count[node][labelIndex] = 1;
24 for (int child : graph.get(node)) {
25 if (child == parent) continue;
26 dfs(child, node, graph, labels, count, result);
27 for (int i = 0; i < 26; i++) {
28 count[node][i] += count[child][i];
29 }
30 }
31 result[node] = count[node][labelIndex];
32 }
33}The Java solution creates a graph using adjacency lists. A depth-first traversal is performed, where a frequency array at each node counts occurrences of each label in the subtree. After recursively merging results from child nodes to the parent, the result for each node is determined by how many times its label appears.
This alternative approach utilizes a HashMap to dynamically manage counts of node labels as opposed to fixed-size arrays. The hash map structure allows potential extension to accommodate varying character sets, though for this problem, it's implemented for the fixed set of labels 'a' to 'z'.
The solution has a time complexity of O(n) given tree node analysis occurs once each during DFS with label counting operations. Space complexity is O(n), due to memory allocations for the graph and storage structures.
1var countSubTrees = function(n, edges, labels) {
2 const graph = Array.from({ length: n }, () => []);
3 for (const [a, b] of edges) {
4 graph[a].push(b);
5 graph[b].push(a);
6 }
7
8 const result = Array(n).fill(0);
9 const count = Array.from({ length: n }, () => new Map());
10
11 const dfs = (node, parent) => {
12 const label = labels[node];
13 count[node].set(label, (count[node].get(label) || 0) + 1);
14 for (const child of graph[node]) {
15 if (child === parent) continue;
16 dfs(child, node);
17 for (const [key, value] of count[child].entries()) {
18 count[node].set(key, (count[node].get(key) || 0) + value);
19 }
20 }
21 result[node] = count[node].get(label);
22 };
23
24 dfs(0, -1);
25 return result;
26};JavaScript's Map provides flexible node count management in this implementation. Employing DFS, the technique dynamically adjusts label frequencies, efficiently merging child findings upward to compute each node's result for its subtree, well accommodated by the map structure.