Number of Good Leaf Nodes Pairs LeetCode solution in Python

1
class Solution:
2
    def countPairs(self, root: TreeNode, distance: int) -> int:
3
        adjList = defaultdict(list)
4
        leaves = []
5
        ct = 0
6

7
        def dfs(node, parent):
8
            if node:
9
                if not node.left and not node.right:
10
                    leaves.append(node)
11
                adjList[node].append(parent)
12
                adjList[parent].append(node)
13
                dfs(node.left, node)
14
                dfs(node.right, node)
15

16
        dfs(root, None)
17

18
        # bfs from each leaf till we find another leaf
19
        for leaf in leaves:
20
            q = deque([(leaf, 0)])
21
            seen = set()
22
            while q:
23
                curr, dist = q.popleft()
24
                seen.add(curr)
25
                if dist > distance:
26
                    break
27
                for nbr in adjList[curr]:
28
                    if nbr and nbr not in seen:
29
                        if nbr in leaves and dist + 1 <= distance:
30
                            ct += 1
31
                        q.append((nbr, dist + 1))
32

33
        return ct // 2