_3249. Count the Number of Good Nodes.md

3249. Count the Number of Good Nodes

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : August 12, 2024

Last updated : August 12, 2024

---

Related Topics : Tree, Depth-First Search

Acceptance Rate : 55.87 %

---

Solutions

• m3249.py

Python

m3249.py

class Solution:
    def countGoodNodes(self, edges: List[List[int]]) -> int:
        adj = defaultdict(list)

        for u, v in edges :
            adj[u].append(v)
            adj[v].append(u)

        def dfs(adj: defaultdict, 
                curr: int = 0, 
                prev: int = -1) -> Tuple[int, int] : # (size of subtree, count)

            if curr > len(edges) :
                return (0, 0)

            output = 0
            size = 1
            vals = set()
            for nxt in adj[curr] :
                if nxt == prev :
                    continue
                brchSize, cnt = dfs(adj, nxt, curr)
                output += cnt
                vals.add(brchSize)
                size += brchSize

            if len(vals) <= 1 :
                output += 1
            return (size, output)

        return dfs(adj)[1]