1519. 子树中标签相同的节点数（Rating 1808）

以下内容偏向于记录个人练习过程及思考，请审慎阅读。

题目

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

Rating 1808

思路

快养成习惯了，看到只有小写字母的题，先想一下有没有O(26X)复杂度的解法。这道题也是一个比较典型的例子。

对于某个节点，如果我们知道这个节点每个子树中对应的26个小写字母出现的次数，那么加上这个节点本身统计一下即可得到这个节点对应的树的26个小写字母出现的次数。这是一个递归的过程，可以使用dfs实现。

对于树的dfs遍历，可以通过记录父节点避免重复访问。

代码

class Solution:
    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
        def dfs(x: int, fa: int): # dfs，x为当前节点，fa为父节点
            nonlocal cnt, g, labels # 声明非局部变量
            cnt[x][ord(labels[x]) - ord('a')] += 1 # 先考虑自身节点的label，cnt += 1
            for y in g[x]: # 遍历子节点
                if y == fa: # 跳过父节点
                    continue
                dfs(y, x) # 递归遍历子节点
                for i in range(26): # 累加子节点对应26个字母的cnt，得到当前节点的cnt
                    cnt[x][i] += cnt[y][i]

        cnt = [[0 for _ in range(26)] for _ in range(n)] # n个节点、26个字母对应的cnt
        g = [[] for _ in range(n)] # 邻接表存树
        for u, v in edges: # 构建树
            g[u].append(v)
            g[v].append(u)
        dfs(0, -1) # 从根节点开始，递归遍历树
        ret = [cnt[i][ord(label) - ord('a')] for i, label in enumerate(labels)] # 按照题目要求统计答案
        return ret