Medium
题目描述
给你一棵树（即一个连通、无向、无环图），这棵树由编号从 0 到 n - 1 的 n 个节点组成，且恰好有 n - 1 条边。树的根节点是节点 0 ，树上每一个节点都有一个标签，也就是字符串 labels 中的一个小写字符（节点 i 的标签就是 labels[i] ）。
边数组 edges 以 edges[i] = [ai, bi] 的形式给出，该格式表示节点 ai 和 bi 之间存在一条边。
返回一个大小为 n 的数组，其中 ans[i] 表示第 i 个节点的子树中与节点 i 标签相同的节点数。
树 T 中的子树是由 T 中的某个节点及其所有后代节点组成的树。
示例 1：
输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
输出：[2,1,1,1,1,1,1]
解释：节点 0 的标签为 'a' ，以 0 为根节点的子树中，节点 2 的标签也为 'a' ，因此答案为 2 。注意树中的每个节点都是这个节点的子树的一部分。
节点 1 的标签为 'b' ，节点 1 的子树包含节点 1、4 和 5，但是节点 4、5 的标签与节点 1 不同，故而答案为 1（即，该节点本身）。
示例 2：
输入：n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
输出：[4,2,1,1]
解释：节点 2 的子树中只有节点 2 ，所以答案为 1 。
节点 3 的子树中只有节点 3 ，所以答案为 1 。
节点 1 的子树中包含节点 1 和 2 ，标签都是 'b' ，因此答案为 2 。
节点 0 的子树中包含节点 0、1、2 和 3，标签都是 'b'，因此答案为 4 。
示例 3：
输入：n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
输出：[3,2,1,1,1]
提示：
- 1 <= n <= 10^5
- edges.length == n - 1
- edges[i].length == 2
- 0 <= ai, bi < n
- ai != bi
- labels.length == n
- labels 仅由小写英文字母组成
解题思路
这是一道典型的树形DP问题。我们需要统计每个节点子树中与该节点标签相同的节点数量。
思路分析：
建图：首先根据edges构建邻接表，表示树的连接关系。
DFS后序遍历：使用深度优先搜索进行后序遍历，这样可以确保在处理父节点时，所有子节点的信息已经计算完毕。
字符计数：每个节点的DFS函数返回一个长度为26的数组，表示以该节点为根的子树中每个字母出现的次数。
状态转移：对于当前节点，先递归处理所有子节点，将所有子节点返回的计数数组相加，再加上当前节点本身的标签计数。
记录答案：在处理每个节点时，从返回的计数数组中提取出与当前节点标签相同的字符计数，这就是答案。
算法流程：
- 从根节点0开始DFS
- 对每个节点，先递归处理所有子节点
- 合并子节点的计数结果，加上当前节点的贡献
- 记录当前节点对应标签的计数到结果数组
- 返回当前子树的完整计数信息给父节点
这种方法的优势是每个节点只访问一次，时间复杂度为O(n)，空间复杂度为O(n)。
代码实现
class Solution {
public:
vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
vector<vector<int>> graph(n);
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
vector<int> result(n);
function<vector<int>(int, int)> dfs = [&](int node, int parent) -> vector<int> {
vector<int> count(26, 0);
for (int child : graph[node]) {
if (child != parent) {
vector<int> childCount = dfs(child, node);
for (int i = 0; i < 26; i++) {
count[i] += childCount[i];
}
}
}
count[labels[node] - 'a']++;
result[node] = count[labels[node] - 'a'];
return count;
};
dfs(0, -1);
return result;
}
};
class Solution:
def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
graph = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
result = [0] * n
def dfs(node, parent):
count = [0] * 26
for child in graph[node]:
if child != parent:
child_count = dfs(child, node)
for i in range(26):
count[i] += child_count[i]
count[ord(labels[node]) - ord('a')] += 1
result[node] = count[ord(labels[node]) - ord('a')]
return count
dfs(0, -1)
return result
public class Solution {
public int[] CountSubTrees(int n, int[][] edges, string labels) {
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
int[] result = new int[n];
int[] Dfs(int node, int parent) {
int[] count = new int[26];
foreach (int child in graph[node]) {
if (child != parent) {
int[] childCount = Dfs(child, node);
for (int i = 0; i < 26; i++) {
count[i] += childCount[i];
}
}
}
count[labels[node] - 'a']++;
result[node] = count[labels[node] - 'a'];
return count;
}
Dfs(0, -1);
return result;
}
}
var countSubTrees = function(n, edges, labels) {
const graph = Array(n).fill(0).map(() => []);
for (const [a, b] of edges) {
graph[a].push(b);
graph[b].push(a);
}
const result = new Array(n).fill(0);
function dfs(node, parent) {
const count = new Array(26).fill(0);
for (const child of graph[node]) {
if (child !== parent) {
const childCount = dfs(child, node);
for (let i = 0; i < 26; i++) {
count[i] += childCount[i];
}
}
}
count[labels.charCodeAt(node) - 97]++;
result[node] = count[labels.charCodeAt(node) - 97];
return count;
}
dfs(0, -1);
return result;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n) - 每个节点访问一次，每次操作为常数时间 |
| 空间复杂度 | O(n) - 图的存储空间 + 递归栈空间 + 结果数组空间 |