3249.统计好节点的数目

链接：3249.统计好节点的数目
难度：Medium
标签：树、深度优先搜索
简介：返回给定树中 好节点 的数量。

题解 1 - undefined

• 编辑时间：2024-11-14
• 执行用时：1048ms
• 内存消耗：126.92MB
• 编程语言：undefined
• 解法介绍：dfs遍历每个子树

class Solution:
    def countGoodNodes(self, edges: List[List[int]]) -> int:
        n = len(edges) + 1
        nodes = [[] for _ in range(n)]
        for n1, n2 in edges:
            nodes[n1].append(n2)
            nodes[n2].append(n1)
        res = 0
        def run(idx: int, p: int) -> int:
            nonlocal res
            arr = [run(child, idx) for child in nodes[idx] if child != p]
            if all([v == arr[0] for v in arr]): res += 1
            return reduce(lambda a, b: a + b, arr, 0) + 1
        run(0, -1)
        return res