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.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6var distanceK = function(root, target, K) {
7 const parentMap = new Map();
8
9 const buildParentMap = (node, parent) => {
10 if (node) {
11 parentMap.set(node, parent);
12 buildParentMap(node.left, node);
13 buildParentMap(node.right, node);
14 }
15 };
16 buildParentMap(root, null);
17
18 const queue = [target];
19 const visited = new Set([target]);
20 let currentLevel = 0;
21
22 while (queue.length) {
23 if (currentLevel === K) {
24 return queue.map(node => node.val);
25 }
26 const size = queue.length;
27 for (let i = 0; i < size; i++) {
28 const node = queue.shift();
29 const directions = [node.left, node.right, parentMap.get(node)];
30 for (const neighbor of directions) {
31 if (neighbor && !visited.has(neighbor)) {
32 visited.add(neighbor);
33 queue.push(neighbor);
34 }
35 }
36 }
37 currentLevel++;
38 }
39 return [];
40};
41This JavaScript solution uses a Map for node-to-parent mapping and employs BFS to explore nodes level by level starting from the target node. A Set ensures nodes aren't revisited, helping prevent infinite cycles within the tree.
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.
1import
This Java solution builds a map associating each node with its parent as it traverses the tree. A DFS search originating from the target node ensures a comprehensive exploration for nodes at distance K, employing a HashSet for tracking visited nodes to prevent redundant checks.