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.
1using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<int> DistanceK(TreeNode root, TreeNode target, int K) {
var parentMap = new Dictionary<TreeNode,TreeNode>();
BuildParentMap(root, null, parentMap);
var result = new List<int>();
var visited = new HashSet<TreeNode>();
Dfs(target, K, null, visited, parentMap, result);
return result;
}
private void BuildParentMap(TreeNode node, TreeNode parent, Dictionary<TreeNode,TreeNode> parentMap) {
if (node != null) {
parentMap[node] = parent;
BuildParentMap(node.left, node, parentMap);
BuildParentMap(node.right, node, parentMap);
}
}
private void Dfs(TreeNode node, int K, TreeNode parent, HashSet<TreeNode> visited, Dictionary<TreeNode,TreeNode> parentMap, IList<int> result) {
if (node == null || visited.Contains(node)) return;
visited.Add(node);
if (K == 0) {
result.Add(node.val);
return;
}
if (node.left != parent) Dfs(node.left, K - 1, node, visited, parentMap, result);
if (node.right != parent) Dfs(node.right, K - 1, node, visited, parentMap, result);
TreeNode parentNode = parentMap[node];
if (parentNode != null && parentNode != parent) Dfs(parentNode, K - 1, node, visited, parentMap, result);
}
}
This C# solution defines a DFS exploration starting from the target, scanning backward through parents using a pre-constructed map. A HashSet is employed to track visited nodes, ensuring every path is explored without repetition.