All Nodes Distance K in Binary Tree LeetCode solution in Python

1
class Solution:
2
    def distanceK(self, root, target, K):
3
        # Step 1: Build adjacency list graph
4
        graph = {}
5
        self.buildGraph(root, None, graph)
6

7
        # Step 2: Perform BFS from the target node
8
        queue = [(target, 0)]
9
        visited = set([target])
10
        result = []
11

12
        while queue:
13
            node, distance = queue.pop(0)
14

15
            if distance == K:
16
                result.append(node.val)
17

18
            if distance > K:
19
                break
20

21
            for neighbor in graph[node]:
22
                if neighbor not in visited:
23
                    visited.add(neighbor)
24
                    queue.append((neighbor, distance + 1))
25

26
        return result
27

28
    def buildGraph(self, node, parent, graph):
29
        if not node:
30
            return
31

32
        if node not in graph:
33
            graph[node] = []
34

35
        if parent:
36
            graph[node].append(parent)
37
            graph[parent].append(node)
38

39
        self.buildGraph(node.left, node, graph)
40
        self.buildGraph(node.right, node, graph)