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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] CountSubTrees(int n, int[][] edges, string labels) {
6 List<int>[] graph = new List<int>[n];
7 for (int i = 0; i < n; i++) {
8 graph[i] = new List<int>();
9 }
10 foreach (var edge in edges) {
11 graph[edge[0]].Add(edge[1]);
12 graph[edge[1]].Add(edge[0]);
13 }
14
15 int[] result = new int[n];
16 int[][] count = new int[n][];
17 for (int i = 0; i < n; i++) {
18 count[i] = new int[26];
19 }
20 Dfs(0, -1, graph, labels, count, result);
21 return result;
22 }
23
24 private void Dfs(int node, int parent, List<int>[] graph, string labels, int[][] count, int[] result) {
25 int labelIndex = labels[node] - 'a';
26 count[node][labelIndex] = 1;
27 foreach (var child in graph[node]) {
28 if (child == parent) continue;
29 Dfs(child, node, graph, labels, count, result);
30 for (int i = 0; i < 26; i++) {
31 count[node][i] += count[child][i];
32 }
33 }
34 result[node] = count[node][labelIndex];
35 }
36}In C#, the algorithm constructs a graph with adjacency lists and uses a depth-first traversal with an integer array to count letter occurrences in each subtree. It recursively accumulates the children's label data at their parent nodes, allowing it to compute the result for every 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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] CountSubTrees(int n, int[][] edges, string labels) {
6 List<int>[] graph = new List<int>[n];
7 for (int i = 0; i < n; i++) {
8 graph[i] = new List<int>();
9 }
10 foreach (var edge in edges) {
11 graph[edge[0]].Add(edge[1]);
12 graph[edge[1]].Add(edge[0]);
13 }
14
15 int[] result = new int[n];
16 List<Dictionary<char, int>> count = new List<Dictionary<char, int>>();
17 for (int i = 0; i < n; i++) {
18 count.Add(new Dictionary<char, int>());
19 }
20 Dfs(0, -1, graph, labels, count, result);
21 return result;
22 }
23
24 private void Dfs(int node, int parent, List<int>[] graph, string labels, List<Dictionary<char, int>> count, int[] result) {
25 char label = labels[node];
26 if (!count[node].ContainsKey(label)) count[node][label] = 0;
27 count[node][label]++;
28
29 foreach (var child in graph[node]) {
30 if (child == parent) continue;
31 Dfs(child, node, graph, labels, count, result);
32 foreach (var keyValue in count[child]) {
33 if (!count[node].ContainsKey(keyValue.Key)) count[node][keyValue.Key] = 0;
34 count[node][keyValue.Key] += keyValue.Value;
35 }
36 }
37
38 result[node] = count[node][label];
39 }
40}C# provides Dictionaries, facilitating dynamic data management in this implementation. As nodes are analyzed in DFS, dictionaries track and update label counts efficiently, aligning computation for each node’s result to all available child data merged iteratively.