题目描述
给了一些点的连通关系，每个点的值都不同，每个点上都哟一个附加的标签（小写字母）
问：每个节点i的子树中标签和i相同的节点数
| f1-无向图后序遍历 |
基本分析
- 怎么根据连接关系进行遍历？先建图
- 遍历的时候没有方向，怎么保证不会回去？加一个父节点的参数，保证不会往前走？
- 怎么维护当前节点的信息？（1）遍历顺序？后序遍历，子节点信息拿到以后，在维护当前节点信息；（2）什么结构？需要f[i][j]表示节点i的第j个字母（0-'a', 1-'b',25-'z'）的出现次数；（3）怎么维护？每个子节点dfs之后，这个节点的信息已知了，[cur]...+= [y]...
- 怎么拿到答案？从f中拿出和当前节点标签相同的点拼起来。
代码
class Solution:
def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
f = [[0]*26 for _ in range(n)]
g = defaultdict(list)
for x, y in edges:
g[x].append(y)
g[y].append(x)
def dfs(cur, par):
# 维护当前节点子树中字符的情况
f[cur][ord(labels[cur]) - ord('a')] += 1
# 枚举子节点
for y in g[cur]:
# 保证不往上跑
if y != par:
dfs(y, cur)
for i in range(26):
f[cur][i] += f[y][i]
dfs(0, -1)
ans = [f[i][ord(labels[i]) - ord('a')] for i in range(n)]
return ans
总结
- 利用edges建图
- dfs时候利用par参数保证不往回走
- 后序遍历，子节点dfs之后，可以认为子节点信息已知，利用以上信息维护当前节点信息