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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public IList<int> DistanceK(TreeNode root, TreeNode target, int K) {
13 var parentMap = new Dictionary<TreeNode, TreeNode>();
14 BuildParentMap(root, parentMap);
15
16 var queue = new Queue<TreeNode>();
17 var visited = new HashSet<TreeNode>();
18 queue.Enqueue(target);
19 visited.Add(target);
20
21 int currentLevel = 0;
22 while (queue.Count > 0) {
23 if (currentLevel == K) {
24 var result = new List<int>();
25 foreach (var node in queue) {
26 result.Add(node.val);
27 }
28 return result;
29 }
30 int size = queue.Count;
31 for (int i = 0; i < size; i++) {
32 var node = queue.Dequeue();
33 foreach (var neighbor in new[] { node.left, node.right, parentMap.ContainsKey(node) ? parentMap[node] : null }) {
34 if (neighbor != null && !visited.Contains(neighbor)) {
35 visited.Add(neighbor);
36 queue.Enqueue(neighbor);
37 }
38 }
39 }
40 currentLevel++;
41 }
42
43 return new List<int>();
44 }
45
46 private void BuildParentMap(TreeNode node, Dictionary<TreeNode, TreeNode> parentMap) {
47 if (node.left != null) {
48 parentMap[node.left] = node;
49 BuildParentMap(node.left, parentMap);
50 }
51 if (node.right != null) {
52 parentMap[node.right] = node;
53 BuildParentMap(node.right, parentMap);
54 }
55 }
56}
57The C# solution constructs a parent map and implements BFS starting from the target node, ensuring nodes are visited level-wise. The HashSet prevents revisiting of previously processed 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.