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.
1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7 vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
8 vector<vector<int>> graph(n);
9 for (const auto& edge : edges) {
10 graph[edge[0]].push_back(edge[1]);
11 graph[edge[1]].push_back(edge[0]);
12 }
13
14 vector<int> result(n, 0);
15 vector<vector<int>> count(n, vector<int>(26, 0));
16 dfs(0, -1, graph, labels, count, result);
17 return result;
18 }
19
20private:
21 void dfs(int node, int parent, vector<vector<int>>& graph, string& labels, vector<vector<int>>& count, vector<int>& result) {
22 int labelIndex = labels[node] - 'a';
23 count[node][labelIndex] = 1;
24 for (int child : graph[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};This C++ solution also employs a DFS to traverse the tree. We build an adjacency list for the graph and use a frequency array for each node to track character counts in the subtree. In the DFS function, we recursively update the frequency array for the current node using the frequency arrays from its child nodes. The result for each node is set to the count of its label in its subtree.
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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5typedef struct {
6 int *counts;
7 int size;
8} CountMap;
9
10CountMap* createCountMap() {
11 CountMap* countMap = (CountMap*)malloc(sizeof(CountMap));
12 countMap->counts = (int*)calloc(26, sizeof(int));
13 countMap->size = 26;
14 return countMap;
15}
16
17void freeCountMap(CountMap* countMap) {
18 free(countMap->counts);
19 free(countMap);
20}
21
22void mergeMaps(CountMap* target, CountMap* source) {
23 for (int i = 0; i < source->size; i++) {
24 target->counts[i] += source->counts[i];
25 }
26}
27
28void dfs(int node, int parent, int** graph, int* graphSize, char* labels, int* result, CountMap** countMaps) {
29 int labelIndex = labels[node] - 'a';
30 countMaps[node]->counts[labelIndex] = 1;
31
32 for (int i = 0; i < graphSize[node]; i++) {
33 int child = graph[node][i];
34 if (child == parent) continue;
35 dfs(child, node, graph, graphSize, labels, result, countMaps);
36 mergeMaps(countMaps[node], countMaps[child]);
37 }
38
39 result[node] = countMaps[node]->counts[labelIndex];
40}
41
42int* countSubTrees(int n, int** edges, int edgesSize, int* edgesColSize, char* labels, int* returnSize) {
43 int** graph = (int**)malloc(n * sizeof(int*));
44 int* graphSize = (int*)calloc(n, sizeof(int));
45 for (int i = 0; i < n; i++) {
46 graph[i] = (int*)malloc(n * sizeof(int));
47 }
48 for (int i = 0; i < edgesSize; i++) {
49 int a = edges[i][0];
50 int b = edges[i][1];
51 graph[a][graphSize[a]++] = b;
52 graph[b][graphSize[b]++] = a;
53 }
54
55 CountMap** countMaps = (CountMap**)malloc(n * sizeof(CountMap*));
56 for (int i = 0; i < n; i++) {
57 countMaps[i] = createCountMap();
58 }
59
60 int* result = (int*)calloc(n, sizeof(int));
61 dfs(0, -1, graph, graphSize, labels, result, countMaps);
62
63 *returnSize = n;
64 for (int i = 0; i < n; i++) {
65 free(graph[i]);
66 freeCountMap(countMaps[i]);
67 }
68 free(graph);
69 free(countMaps);
70 free(graphSize);
71 return result;
72}This C solution replaces the fixed array used for counting character occurrences with dynamically sized CountMap structures, implementing a merge function to combine results from child nodes into their parent node's structure during DFS. Each node manages its own label counts, which are summed in the result array.