123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123
#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:
// Method to burn the tree starting from a given node
int timeToBurnTree(TreeNode* root, int start) {
// Create a map to store the parent nodes
unordered_map<TreeNode*, TreeNode*> mpp;
// Get the target node (starting node for burning)
TreeNode* target = bfsToMapParents(root, mpp, start);
// Find the maximum distance to burn the tree
int maxi = findMaxDistance(mpp, target);
return maxi;
}
private:
// Method to map parents of all nodes using BFS
TreeNode* bfsToMapParents(TreeNode* root, unordered_map<TreeNode*, TreeNode*>& mpp, int start) {
// Queue for BFS
queue<TreeNode*> q;
// Push the root node to the queue
q.push(root);
TreeNode* res = new TreeNode(-1);
while (!q.empty()) {
// Get the front node from the queue
TreeNode* node = q.front();
q.pop();
// Check if this is the start node
if (node->data == start) res = node;
// Map the left child to its parent
if (node->left != nullptr) {
mpp[node->left] = node;
q.push(node->left);
}
// Map the right child to its parent
if (node->right != nullptr) {
mpp[node->right] = node;
q.push(node->right);
}
}
return res;
}
// Method to find the maximum distance to burn the tree
int findMaxDistance(unordered_map<TreeNode*, TreeNode*>& mpp, TreeNode* target) {
// Queue for BFS to find max distance
queue<TreeNode*> q;
q.push(target);
// Map to check visited nodes
unordered_map<TreeNode*, int> vis;
vis[target] = 1;
int maxi = 0;
while (!q.empty()) {
int size = q.size();
int fl = 0;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
// Check left child
if (node->left != nullptr && vis.find(node->left) == vis.end()) {
fl = 1;
vis[node->left] = 1;
q.push(node->left);
}
// Check right child
if (node->right != nullptr && vis.find(node->right) == vis.end()) {
fl = 1;
vis[node->right] = 1;
q.push(node->right);
}
// Check parent node
if (mpp.find(node) != mpp.end() && vis.find(mpp[node]) == vis.end()) {
fl = 1;
vis[mpp[node]] = 1;
q.push(mpp[node]);
}
}
// Increment max distance if any node was burned
if (fl == 1) maxi++;
}
return maxi;
}
};
// Main method to test the functionality
int main() {
Solution sol;
// Create the binary tree
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
int start = 4;
// Get the time to burn the tree
int result = sol.timeToBurnTree(root, start);
cout << "Time to burn the tree: " << result << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119
/**
* Definition for a binary tree node.
*/
public class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int val) {
data = val;
left = null;
right = null;
}
}
class Solution {
// Method to burn the tree starting from a given node
public int timeToBurnTree(TreeNode root, int start) {
// Create a map to store the parent nodes
HashMap<TreeNode, TreeNode> mpp = new HashMap<>();
// Get the target node (starting node for burning)
TreeNode target = bfsToMapParents(root, mpp, start);
// Find the maximum distance to burn the tree
int maxi = findMaxDistance(mpp, target);
return maxi;
}
// Method to map parents of all nodes using BFS
private TreeNode bfsToMapParents(TreeNode root, HashMap<TreeNode, TreeNode> mpp, int start) {
// Queue for BFS
Queue<TreeNode> q = new LinkedList<>();
// Push the root node to the queue
q.offer(root);
TreeNode res = new TreeNode(-1);
while (!q.isEmpty()) {
// Get the front node from the queue
TreeNode node = q.poll();
// Check if this is the start node
if (node.data == start) res = node;
// Map the left child to its parent
if (node.left != null) {
mpp.put(node.left, node);
q.offer(node.left);
}
// Map the right child to its parent
if (node.right != null) {
mpp.put(node.right, node);
q.offer(node.right);
}
}
return res;
}
// Method to find the maximum distance to burn the tree
private int findMaxDistance(HashMap<TreeNode, TreeNode> mpp, TreeNode target) {
// Queue for BFS to find max distance
Queue<TreeNode> q = new LinkedList<>();
q.offer(target);
// Map to check visited nodes
HashMap<TreeNode, Integer> vis = new HashMap<>();
vis.put(target, 1);
int maxi = 0;
while (!q.isEmpty()) {
int size = q.size();
int fl = 0;
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
// Check left child
if (node.left != null && vis.get(node.left) == null) {
fl = 1;
vis.put(node.left, 1);
q.offer(node.left);
}
// Check right child
if (node.right != null && vis.get(node.right) == null) {
fl = 1;
vis.put(node.right, 1);
q.offer(node.right);
}
// Check parent node
if (mpp.get(node) != null && vis.get(mpp.get(node)) == null) {
fl = 1;
vis.put(mpp.get(node), 1);
q.offer(mpp.get(node));
}
}
// Increment max distance if any node was burned
if (fl == 1) maxi++;
}
return maxi;
}
// Main method to test the functionality
public static void main(String[] args) {
Solution sol = new Solution();
// Create the binary tree
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
int start = 4;
// Get the time to burn the tree
int result = sol.timeToBurnTree(root, start);
System.out.println("Time to burn the tree: " + result);
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.data = val
self.left = left
self.right = right
class Solution:
def timeToBurnTree(self, root, start):
# Map to store parent nodes
mpp = {}
# Get the target node (starting node for burning)
target = self.bfsToMapParents(root, mpp, start)
# Find the maximum distance to burn the tree
maxi = self.findMaxDistance(mpp, target)
return maxi
# Method to map parents of all nodes using BFS
def bfsToMapParents(self, root, mpp, start):
# Queue for BFS
q = [root]
res = None
while q:
# Get the front node from the queue
node = q.pop(0)
# Check if this is the start node
if node.data == start:
res = node
# Map the left child to its parent
if node.left:
mpp[node.left] = node
q.append(node.left)
# Map the right child to its parent
if node.right:
mpp[node.right] = node
q.append(node.right)
return res
# Method to find the maximum distance to burn the tree
def findMaxDistance(self, mpp, target):
# Queue for BFS to find max distance
q = [target]
# Set to check visited nodes
vis = {target}
maxi = 0
while q:
size = len(q)
fl = 0
for _ in range(size):
node = q.pop(0)
# Check left child
if node.left and node.left not in vis:
fl = 1
vis.add(node.left)
q.append(node.left)
# Check right child
if node.right and node.right not in vis:
fl = 1
vis.add(node.right)
q.append(node.right)
# Check parent node
if node in mpp and mpp[node] not in vis:
fl = 1
vis.add(mpp[node])
q.append(mpp[node])
# Increment max distance if any node was burned
if fl == 1:
maxi += 1
return maxi
# Main function to test the functionality
if __name__ == "__main__":
sol = Solution()
# Create the binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
start = 4
# Get the time to burn the tree
result = sol.timeToBurnTree(root, start)
print("Time to burn the tree:", result)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116
/**
* 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 {
// Method to burn the tree starting from a given node
timeToBurnTree(root, start) {
// Map to store parent nodes
let mpp = new Map();
// Get the target node (starting node for burning)
let target = this.bfsToMapParents(root, mpp, start);
// Find the maximum distance to burn the tree
let maxi = this.findMaxDistance(mpp, target);
return maxi;
}
// Method to map parents of all nodes using BFS
bfsToMapParents(root, mpp, start) {
// Queue for BFS
let q = [root];
let res = null;
while (q.length > 0) {
// Get the front node from the queue
let node = q.shift();
// Check if this is the start node
if (node.data === start) {
res = node;
}
// Map the left child to its parent
if (node.left !== null) {
mpp.set(node.left, node);
q.push(node.left);
}
// Map the right child to its parent
if (node.right !== null) {
mpp.set(node.right, node);
q.push(node.right);
}
}
return res;
}
// Method to find the maximum distance to burn the tree
findMaxDistance(mpp, target) {
// Queue for BFS to find max distance
let q = [target];
// Set to check visited nodes
let vis = new Set();
vis.add(target);
let maxi = 0;
while (q.length > 0) {
let size = q.length;
let fl = 0;
for (let i = 0; i < size; i++) {
let node = q.shift();
// Check left child
if (node.left !== null && !vis.has(node.left)) {
fl = 1;
vis.add(node.left);
q.push(node.left);
}
// Check right child
if (node.right !== null && !vis.has(node.right)) {
fl = 1;
vis.add(node.right);
q.push(node.right);
}
// Check parent node
if (mpp.has(node) && !vis.has(mpp.get(node))) {
fl = 1;
vis.add(mpp.get(node));
q.push(mpp.get(node));
}
}
// Increment max distance if any node was burned
if (fl === 1) {
maxi++;
}
}
return maxi;
}
}
// Main function to test the functionality
(function() {
let sol = new Solution();
// Create the binary tree
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
let start = 4;
// Get the time to burn the tree
let result = sol.timeToBurnTree(root, start);
console.log("Time to burn the tree:", result);
})();
