1519. Number of Nodes in the Sub-Tree With the Same Label
给你一棵树 每个 node 都带有编号和一个字符
要你对每个 node 找出他们的子树中有多少 node 和他有一样的字符
自己也包含在内
Example 1:
https://assets.leetcode.com/uploads/2020/07/01/q3e1.jpg
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels =
"abaedcd"
Output: [2,1,1,1,1,1,1]
以 node 0 为顶点的树中有两个 label[0] = 'a' 其他都只有一个
Example 2:
https://assets.leetcode.com/uploads/2020/07/01/q3e2.jpg
Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Example 3:
https://assets.leetcode.com/uploads/2020/07/01/q3e3.jpg
Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]
思路:
1.对每个 node 都需要知道以他们为顶点的子树 各个字符的数量 用 dict(node) 代表
如果对每个 node 都遍历整棵子树算出 dict(node) 时间复杂度会是O(n^2)太高
可以在 dfs child 的时候回传以 child 为顶点的子树的 dict(child)
这样就不用每个 node 都重算一次
最后看 dict(node) 中 key = label[node] 的 value 是多少就好
2.为了不在 dfs 的时候往回走可以记一下目前 node 的 parent
当然也可以用 visited 去记
Python code:
class Solution:
def countSubTrees(self, n: int, edges: List[List[int]], labels: str) ->
List[int]:
neighbor = defaultdict(list)
for a, b in edges:
neighbor[a].append(b)
neighbor[b].append(a)
res = [0]*n
def dfs(node, parent):
count = Counter(labels[node])
for nb in neighbor[node]:
if nb != parent:
count += dfs(nb, node)
res[node] = count[labels[node]]
return count
dfs(0, -1)
return res
今天第一次知道 Counter() 可以直接用加的...