Sponsored
Sponsored
In this method, we first traverse the tree to establish a mapping of each node to its parent. This will allow us to easily move upwards in the tree. We then perform a BFS starting from the target node to explore all nodes at distance K. Using a queue to explore nodes level by level ensures we can track the distance from the target correctly.
Time Complexity: O(N), where N is the number of nodes, since each node is visited once. Space Complexity: O(N) for storing the parent map and the queue.
1from collections import deque, defaultdict
2
3class TreeNode:
4 def __init__(self, x):
5 self.val = x
6 self.left = None
7 self.right = None
8
9class Solution:
10 def distanceK(self, root, target, K):
11 parent_map = {}
12 self.buildParentMap(root, None, parent_map)
13
14 queue = deque([target])
15 visited = set([target])
16 current_level = 0
17
18 while queue:
19 if current_level == K:
20 return [node.val for node in queue]
21 size = len(queue)
22 for i in range(size):
23 node = queue.popleft()
24 for neighbor in (node.left, node.right, parent_map.get(node, None)):
25 if neighbor and neighbor not in visited:
26 visited.add(neighbor)
27 queue.append(neighbor)
28 current_level += 1
29
30 return []
31
32 def buildParentMap(self, node, parent, parent_map):
33 if node:
34 parent_map[node] = parent
35 self.buildParentMap(node.left, node, parent_map)
36 self.buildParentMap(node.right, node, parent_map)
37This Python solution establishes a map associating each node to its parent. Utilizing BFS from the target node, it systematically checks left, right, and parent nodes while avoiding revisiting by recording visited nodes.
In this method, we perform a DFS from the root to find the path to the target node while also tracking parents of each node. We then use this path to initiate DFS from the target node in all possible directions (left, right, up) to find nodes that are K distance away.
Time Complexity: O(N), traversing the tree requires visiting each node once. Space Complexity: O(N) for the parent map and the recursion call stack.
1class
This Python approach starts by creating a parent map during a DFS traversal. Commencing from the target node, it executes another DFS to locate all nodes at distance K, avoiding repeated visits via a set collection.