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.
1#include <iostream>
2#include <unordered_map>
3#include <unordered_set>
4#include <vector>
5#include <queue>
6using namespace std;
7
8struct TreeNode {
9 int val;
10 TreeNode* left;
11 TreeNode* right;
12 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
13};
14
15void buildParentMap(TreeNode* root, unordered_map<TreeNode*, TreeNode*>& parentMap) {
16 if (!root) return;
17 if (root->left) {
18 parentMap[root->left] = root;
19 buildParentMap(root->left, parentMap);
20 }
21 if (root->right) {
22 parentMap[root->right] = root;
23 buildParentMap(root->right, parentMap);
24 }
25}
26
27vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
28 unordered_map<TreeNode*, TreeNode*> parentMap;
29 buildParentMap(root, parentMap);
30
31 queue<pair<TreeNode*, int>> q;
32 unordered_set<TreeNode*> visited;
33 q.push({target, 0});
34 visited.insert(target);
35
36 vector<int> result;
37 while (!q.empty()) {
38 pair<TreeNode*, int> current = q.front(); q.pop();
39 TreeNode* node = current.first;
40 int distance = current.second;
41
42 if (distance == K) {
43 result.push_back(node->val);
44 }
45
46 if (distance > K) break;
47
48 // Check left child
49 if (node->left && !visited.count(node->left)) {
50 q.push({node->left, distance + 1});
51 visited.insert(node->left);
52 }
53
54 // Check right child
55 if (node->right && !visited.count(node->right)) {
56 q.push({node->right, distance + 1});
57 visited.insert(node->right);
58 }
59
60 // Check parent
61 if (parentMap.find(node) != parentMap.end() && !visited.count(parentMap[node])) {
62 q.push({parentMap[node], distance + 1});
63 visited.insert(parentMap[node]);
64 }
65 }
66
67 return result;
68}
69In this C++ solution, we construct a map that links each node to its parent. A BFS traversal begins from the target node to discover all nodes at distance K, ensuring visited nodes are tracked to avoid revisiting in cycles.
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.