123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
#include<bits/stdc++.h>
using namespace std;
/**
* Definition for a binary tree node.
*/
struct TreeNode {
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
// Step 1: Create a map to store the parent of each node
unordered_map<TreeNode*, TreeNode*> parentMap;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
// If the left child exists, map its parent and push it into the queue
if (node->left) {
parentMap[node->left] = node;
q.push(node->left);
}
// If the right child exists, map its parent and push it into the queue
if (node->right) {
parentMap[node->right] = node;
q.push(node->right);
}
}
// Step 2: Use BFS to find all nodes at distance k from the target
vector<int> result;
unordered_set<TreeNode*> visited;
q.push(target);
visited.insert(target);
int currentDistance = 0;
// Continue BFS until the desired distance is reached
while (!q.empty()) {
if (currentDistance == k) {
// Collect all nodes at distance k
while (!q.empty()) {
result.push_back(q.front()->data);
q.pop();
}
return result;
}
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
// Check left child
if (node->left && visited.find(node->left) == visited.end()) {
q.push(node->left);
visited.insert(node->left);
}
// Check right child
if (node->right && visited.find(node->right) == visited.end()) {
q.push(node->right);
visited.insert(node->right);
}
// Check parent
if (parentMap.find(node) != parentMap.end() && visited.find(parentMap[node]) == visited.end()) {
q.push(parentMap[node]);
visited.insert(parentMap[node]);
}
}
currentDistance++;
}
return result;
}
};
// Helper function to create a binary tree from a vector
TreeNode* createTree(const vector<int>& nodes, int index = 0) {
if (index < nodes.size() && nodes[index] != -1) {
TreeNode* root = new TreeNode(nodes[index]);
root->left = createTree(nodes, 2 * index + 1);
root->right = createTree(nodes, 2 * index + 2);
return root;
}
return nullptr;
}
int main() {
vector<int> nodes = {3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4};
TreeNode* root = createTree(nodes);
TreeNode* target = root->left; // Node with value 5
int k = 2;
Solution sol;
vector<int> result = sol.distanceK(root, target, k);
cout << "Nodes at distance " << k << " from target node are: ";
for (int val : result) {
cout << val << " ";
}
cout << endl;
return 0;
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
import java.util.*;
/**
* Definition for a binary tree node.
*/
class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int val) { data = val; left = null; right = null; }
}
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
// Step 1: Create a map to store the parent of each node
Map<TreeNode, TreeNode> parentMap = new HashMap<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// If the left child exists, map its parent and push it into the queue
if (node.left != null) {
parentMap.put(node.left, node);
queue.add(node.left);
}
// If the right child exists, map its parent and push it into the queue
if (node.right != null) {
parentMap.put(node.right, node);
queue.add(node.right);
}
}
// Step 2: Use BFS to find all nodes at distance k from the target
List<Integer> result = new ArrayList<>();
Set<TreeNode> visited = new HashSet<>();
queue.add(target);
visited.add(target);
int currentDistance = 0;
// Continue BFS until the desired distance is reached
while (!queue.isEmpty()) {
if (currentDistance == k) {
// Collect all nodes at distance k
while (!queue.isEmpty()) {
result.add(queue.poll().data);
}
return result;
}
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
// Check left child
if (node.left != null && !visited.contains(node.left)) {
queue.add(node.left);
visited.add(node.left);
}
// Check right child
if (node.right != null && !visited.contains(node.right)) {
queue.add(node.right);
visited.add(node.right);
}
// Check parent
if (parentMap.containsKey(node) && !visited.contains(parentMap.get(node))) {
queue.add(parentMap.get(node));
visited.add(parentMap.get(node));
}
}
currentDistance++;
}
return result;
}
// Helper function to create a binary tree from a list
public static TreeNode createTree(List<Integer> nodes, int index) {
if (index < nodes.size() && nodes.get(index) != null) {
TreeNode root = new TreeNode(nodes.get(index));
root.left = createTree(nodes, 2 * index + 1);
root.right = createTree(nodes, 2 * index + 2);
return root;
}
return null;
}
public static void main(String[] args) {
List<Integer> nodes = Arrays.asList(3, 5, 1, 6, 2, 0, 8, null, null, 7, 4);
TreeNode root = createTree(nodes, 0);
TreeNode target = root.left; // Node with value 5
int k = 2;
Solution sol = new Solution();
List<Integer> result = sol.distanceK(root, target, k);
System.out.println("Nodes at distance " + k + " from target node are: " + result);
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
from collections import deque, defaultdict
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.data = val
self.left = left
self.right = right
class Solution:
def distanceK(self, root, target, k):
# Step 1: Create a map to store the parent of each node
parent_map = {}
queue = deque([root])
while queue:
node = queue.popleft()
if node.left:
parent_map[node.left] = node
queue.append(node.left)
if node.right:
parent_map[node.right] = node
queue.append(node.right)
# Step 2: Use BFS to find all nodes at distance k from the target
result = []
visited = set()
queue = deque([target])
visited.add(target)
current_distance = 0
# Continue BFS until the desired distance is reached
while queue:
if current_distance == k:
# Collect all nodes at distance k
result.extend(node.data for node in queue)
return result
for _ in range(len(queue)):
node = queue.popleft()
# Check left child
if node.left and node.left not in visited:
visited.add(node.left)
queue.append(node.left)
# Check right child
if node.right and node.right not in visited:
visited.add(node.right)
queue.append(node.right)
# Check parent
if node in parent_map and parent_map[node] not in visited:
visited.add(parent_map[node])
queue.append(parent_map[node])
current_distance += 1
return result
# Helper function to create a binary tree from a list
def create_tree(nodes, index=0):
if index < len(nodes) and nodes[index] is not None:
root = TreeNode(nodes[index])
root.left = create_tree(nodes, 2 * index + 1)
root.right = create_tree(nodes, 2 * index + 2)
return root
return None
def main():
nodes = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]
root = create_tree(nodes)
target = root.left # Node with value 5
k = 2
sol = Solution()
result = sol.distanceK(root, target, k)
print(f"Nodes at distance {k} from target node are: {result}")
if __name__ == "__main__":
main()
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
/**
* Definition for a binary tree node.
*/
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.data = val;
this.left = left;
this.right = right;
}
}
class Solution {
distanceK(root, target, k) {
// Step 1: Create a map to store the parent of each node
const parentMap = new Map();
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
// If the left child exists, map its parent and push it into the queue
if (node.left) {
parentMap.set(node.left, node);
queue.push(node.left);
}
// If the right child exists, map its parent and push it into the queue
if (node.right) {
parentMap.set(node.right, node);
queue.push(node.right);
}
}
// Step 2: Use BFS to find all nodes at distance k from the target
const result = [];
const visited = new Set();
queue.push(target);
visited.add(target);
let currentDistance = 0;
// Continue BFS until the desired distance is reached
while (queue.length > 0) {
if (currentDistance === k) {
// Collect all nodes at distance k
for (const node of queue) {
result.push(node.data);
}
return result;
}
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
// Check left child
if (node.left && !visited.has(node.left)) {
queue.push(node.left);
visited.add(node.left);
}
// Check right child
if (node.right && !visited.has(node.right)) {
queue.push(node.right);
visited.add(node.right);
}
// Check parent
if (parentMap.has(node) && !visited.has(parentMap.get(node))) {
queue.push(parentMap.get(node));
visited.add(parentMap.get(node));
}
}
currentDistance++;
}
return result;
}
}
// Helper function to create a binary tree from an array
function createTree(nodes, index = 0) {
if (index < nodes.length && nodes[index] !== null) {
const root = new TreeNode(nodes[index]);
root.left = createTree(nodes, 2 * index + 1);
root.right = createTree(nodes, 2 * index + 2);
return root;
}
return null;
}
// Main function to test the distanceK method
function main() {
const nodes = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4];
const root = createTree(nodes);
const target = root.left; // Node with value 5
const k = 2;
const sol = new Solution();
const result = sol.distanceK(root, target, k);
console.log(`Nodes at distance ${k} from target node are: ${result}`);
}
// Run the main function
main();
