---

1519. 子树中标签相同的节点数

• 标签：树、深度优先搜索、广度优先搜索、哈希表、计数
• 难度：中等

题目链接

• 1519. 子树中标签相同的节点数 - 力扣

题目大意

描述：给定一棵 $n$ 个节点的树（编号 $0 \sim n-1$），根节点为 $0$。每个节点有一个小写字母标签 $labels[i]$。给定无向边 $edges$。

要求：返回一个数组 $ans$，其中 $ans[i]$ 表示节点 $i$ 的子树中与 $labels[i]$ 相同标签的节点数（包括节点 $i$ 自身）。

说明：

• $1 \le n \le 10^5$。
• $edges.length = n - 1$。

示例：

• 示例 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' ，以 'a' 为根节点的子树中，节点 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 。

解题思路

思路 1：DFS + 计数

1. 核心思想

从根节点 $0$ 开始 DFS，后序遍历。对每个节点，递归统计子树中每个字母出现的次数，然后返回并累加到父节点。

具体地，$dfs(node)$ 返回一个长度为 $26$ 的数组 $cnt$，表示 $node$ 子树中每个字母的出现次数。

2. 具体步骤

第 1 步：建无向图（邻接表）。

第 2 步：从根节点 $0$ 开始 DFS，使用 $visited$ 防止走回父节点。

第 3 步：对每个节点：

• 初始化 $cnt$ 数组全 $0$。
• 遍历所有邻居（排除父节点），递归得到子节点的计数，逐字母累加。
• $cnt[label[node]] += 1$（节点自身）。
• $ans[node] = cnt[label[node]]$。

第 4 步：返回 $ans$。

3. 举例说明

以 $n=7, edges=[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels="abaedcd"$ 为例：

    0(a)
   / \
  1(b) 2(a)
 / \   / \
4(e)5(d) 3(d)6(c)

• 节点 $4$：'e'，子树中自身计数 $1$。
• 节点 $5$：'d'，子树中自身计数 $1$。
• 节点 $1$：'b'，子树中 'b':1, 'e':1, 'd':1，$ans[1]=1$。
• 节点 $3$：'d'，子树中自身计数 $1$。
• 节点 $6$：'c'，子树中自身计数 $1$。
• 节点 $2$：'a'，子树中 'a':1, 'd':1, 'c':1，$ans[2]=1$。
• 节点 $0$：'a'，子树中 'a':2（自身 $+$ 节点 $2$ 中的 'a'），'b':1, 'e':1, 'd':2, 'c':1，$ans[0]=2$。

思路 1：代码

class Solution:
    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        ans = [0] * n
        visited = [False] * n

        def dfs(u):
            visited[u] = True
            cnt = [0] * 26
            for v in graph[u]:
                if not visited[v]:
                    child_cnt = dfs(v)
                    for i in range(26):
                        cnt[i] += child_cnt[i]
            idx = ord(labels[u]) - 97
            cnt[idx] += 1
            ans[u] = cnt[idx]
            return cnt

        dfs(0)
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n \times 26) = O(n)$。
• 空间复杂度：$O(n \times 26)$，递归栈和计数数组。