給出一棵樹(shù)的所有邊的集合edges、節(jié)點(diǎn)數(shù)、每個(gè)節(jié)點(diǎn)的label（英文小寫(xiě)字母）、0為根節(jié)點(diǎn)、問(wèn)每個(gè)節(jié)點(diǎn)的子樹(shù)中有多少個(gè)節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的label值一樣（包含當(dāng)前節(jié)點(diǎn)）
先根據(jù)edges建樹(shù)(用dict存每個(gè)節(jié)點(diǎn)的鄰接節(jié)點(diǎn)），然后從根開(kāi)始DFS，用Counter()記錄每個(gè)節(jié)點(diǎn)的子樹(shù)中各個(gè)label的節(jié)點(diǎn)數(shù)的計(jì)數(shù)
1 #1519
2 #Runtime: 3033 ms (Beats 71.43%)
3 #Memory: 182.4 MB (Beats 57.14%)
4
5 class Solution(object):
6 def countSubTrees(self, n, edges, labels):
7 """
8 :type n: int
9 :type edges: List[List[int]]
10 :type labels: str
11 :rtype: List[int]
12 """
13 ans = [0] * n
14 node = defaultdict(list)
15 for x, y in edges:
16 node[x].append(y)
17 node[y].append(x)
18
19 def DFS(r, p):
20 cnt = Counter()
21 for i in node[r]:
22 if i != p:
23 cnt += DFS(i, r)
24 cnt[labels[r]] += 1
25 ans[r] = cnt[labels[r]]
26 return cnt
27
28 DFS(0, -1)
29 return ans
30