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.
1from collections import defaultdict
2
3class Solution:
4 def countSubTrees(self, n, edges, labels):
5 tree = defaultdict(list)
6 for a, b in edges:
7 tree[a].append(b)
8 tree[b].append(a)
9
10 result = [0] * n
11 count = [[0] * 26 for _ in range(n)]
12
13 def dfs(node, parent):
14 label_index = ord(labels[node]) - ord('a')
15 count[node][label_index] = 1
16 for child in tree[node]:
17 if child != parent:
18 dfs(child, node)
19 for i in range(26):
20 count[node][i] += count[child][i]
21 result[node] = count[node][label_index]
22
23 dfs(0, -1)
24 return result
25The Python solution constructs a tree using a defaultdict. The DFS traversal is used to keep a frequency array storing label counts for each node's subtree. As the function moves from child to parent nodes, it updates the current node's counts using its children's data. This is used to determine the result for each node.
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.
1import java.util.*;
2
3class Solution {
4 public int[] countSubTrees(int n, int[][] edges, String labels) {
5 List<List<Integer>> graph = new ArrayList<>();
6 for (int i = 0; i < n; i++) {
7 graph.add(new ArrayList<>());
8 }
9 for (int[] edge : edges) {
10 graph.get(edge[0]).add(edge[1]);
11 graph.get(edge[1]).add(edge[0]);
12 }
13
14 int[] result = new int[n];
15 List<Map<Character, Integer>> count = new ArrayList<>();
16 for (int i = 0; i < n; i++) {
17 count.add(new HashMap<>());
18 }
19 dfs(0, -1, graph, labels, count, result);
20 return result;
21 }
22
23 private void dfs(int node, int parent, List<List<Integer>> graph, String labels, List<Map<Character, Integer>> count, int[] result) {
24 char label = labels.charAt(node);
25 count.get(node).put(label, count.get(node).getOrDefault(label, 0) + 1);
26 for (int child : graph.get(node)) {
27 if (child == parent) continue;
28 dfs(child, node, graph, labels, count, result);
29 for (Map.Entry<Character, Integer> entry : count.get(child).entrySet()) {
30 count.get(node).put(entry.getKey(), count.get(node).getOrDefault(entry.getKey(), 0) + entry.getValue());
31 }
32 }
33 result[node] = count.get(node).get(label);
34 }
35}Using Java's HashMap, this distinct solution counts label occurrences across a node’s subtree and propagates this information during DFS, integrating results dynamically based on computed child data. This flexible map-based approach effectively manages counts for each character encountered.