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.
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 }, () => Array(26).fill(0));
10
11 const dfs = (node, parent) => {
12 const labelIndex = labels.charCodeAt(node) - 'a'.charCodeAt(0);
13 count[node][labelIndex] = 1;
14 for (const child of graph[node]) {
15 if (child === parent) continue;
16 dfs(child, node);
17 for (let i = 0; i < 26; i++) {
18 count[node][i] += count[child][i];
19 }
20 }
21 result[node] = count[node][labelIndex];
22 };
23
24 dfs(0, -1);
25 return result;
26};In JavaScript, the tree is represented using an adjacency list. DFS traversal is run from the root node. For each node, a frequency array tracks the occurrence of labels in its subtree. The children's frequency is merged at the parent node using recursion to arrive at the final 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.
1#include <vector>
2#include <unordered_map>
3#include <string>
4using namespace std;
5
6class Solution {
7public:
8 vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
9 vector<vector<int>> graph(n);
10 for (auto& edge : edges) {
11 graph[edge[0]].push_back(edge[1]);
12 graph[edge[1]].push_back(edge[0]);
13 }
14 vector<int> result(n, 0);
15 vector<unordered_map<char, int>> count(n);
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<unordered_map<char, int>>& count, vector<int>& result) {
22 char label = labels[node];
23 count[node][label] = 1;
24 for (int child : graph[node]) {
25 if (child == parent) continue;
26 dfs(child, node, graph, labels, count, result);
27 for (auto& [key, value] : count[child]) {
28 count[node][key] += value;
29 }
30 }
31 result[node] = count[node][label];
32 }
33};The C++ implementation uses a map to manage dynamic label counts. The DFS recursions traverse nodes and merge child data into parents, allowing flexible character count storage and calculations to deliver output with label occurrences per subtree rooted at the respective nodes.