Dado un árbol binario y un Node hoja de este árbol. Se sabe que en 1s todos los Nodes conectados a un Node dado (hijo izquierdo, hijo derecho y padre) se queman en 1 segundo. Luego, todos los Nodes que están conectados a través de un intermediario se queman en 2 segundos, y así sucesivamente. La tarea es encontrar el tiempo mínimo requerido para quemar el árbol binario completo.
Ejemplos:
Input :
1
/ \
2 3
/ \ \
4 5 6
/ \ \
7 8 9
\
10
Leaf = 8
Output : 7
Initially 8 is set to fire at 0th sec.
1
/ \
2 3
/ \ \
4 5 6
/ \ \
7 F 9
\
10
After 1s: 5 is set to fire.
1
/ \
2 3
/ \ \
4 F 6
/ \ \
7 F 9
\
10
After 2s: 2, 7 are set to fire.
1
/ \
F 3
/ \ \
4 F 6
/ \ \
F F 9
\
10
After 3s: 4, 1 are set to fire.
F
/ \
F 3
/ \ \
F F 6
/ \ \
F F 9
\
10
After 4s: 3 is set to fire.
F
/ \
F F
/ \ \
F F 6
/ \ \
F F 9
\
10
After 5s: 6 is set to fire.
F
/ \
F F
/ \ \
F F F
/ \ \
F F 9
\
10
After 6s: 9 is set to fire.
F
/ \
F F
/ \ \
F F F
/ \ \
F F F
\
10
After 7s: 10 is set to fire.
F
/ \
F F
/ \ \
F F F
/ \ \
F F F
\
F
It takes 7s to burn the complete tree.
La idea es almacenar información adicional para cada Node:
- Profundidad del subárbol izquierdo.
- Profundidad del subárbol derecho.
- El tiempo requerido para que el fuego alcance el Node actual a partir del primer Node de hoja quemado.
- Una variable booleana para verificar si el Node quemado inicial está en el árbol enraizado en el Node actual.
Antes de continuar con el enfoque, echemos un vistazo al árbol a continuación:
1
/ \
2 3
/ \ /
4 5 6
/ / \
8 9 10
/
11
En el árbol anterior, si incendiamos el Node hoja 11.
- En 1s, el fuego llegará al Node 9.
- En 2s, el fuego llegará al Node 5.
- En el tercer segundo, el fuego alcanzará los Nodes 2 y 10. Aquí viene una observación:
- En 2s, el fuego alcanzó el Node 5. Para el Node 5, la hoja quemada inicial está en su subárbol izquierdo, por lo que el tiempo necesario para quemar el subárbol derecho será la altura del subárbol derecho, que es 1. Por lo tanto, el fuego llega al Node 10 en ( 2+1) = 3 s.
- Nuevamente, para el Node 2. El fuego alcanzó el Node 2 en 3 segundos desde el subárbol derecho. Por lo tanto, el tiempo necesario para quemar el subárbol izquierdo será su altura.
Entonces, la solución es aplicar la recursividad y, para cada Node, calcular los valores requeridos a continuación:
- Profundidad Izquierda.
- Profundidad correcta.
- El tiempo requerido para que el fuego llegue al Node actual.
- ¿El subárbol actual contiene el Node de hoja quemado inicial?
Entonces, el tiempo mínimo requerido para grabar cualquier subárbol será:
El tiempo requerido para que el fuego llegue al nudo raíz desde la hoja quemada inicial + profundidad del lado opuesto
Por lo tanto, para encontrar el tiempo requerido para quemar el árbol completo, necesitamos calcular el valor anterior para cada Node y tomar el máximo de ese valor.
ans = max(ans, (tiempo requerido para que el fuego alcance el Node actual + profundidad de otro subárbol))
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find minimum time required
// to burn the binary tree completely
#include <bits/stdc++.h>
using namespace std;
// Tree Node
struct Node {
int data;
Node* left;
Node* right;
Node()
{
left = NULL;
right = NULL;
}
};
// Utility function to create a new Node
Node* newNode(int val)
{
Node* temp = new Node;
temp->data = val;
return temp;
}
/*
***********ADDITIONAL INFO*************
lDepth - maximum height of left subtree
rDepth - maximum height of right subtree
contains - stores true if tree rooted at current
node contains the first burnt node time - time to reach
fire from the initially burnt leaf node to this node
*/
struct Info {
int lDepth;
int rDepth;
bool contains;
int time;
Info()
{
lDepth = rDepth = 0;
contains = false;
time = -1;
}
};
/*
Function to calculate time required to burn
tree completely
node - address of current node
info - extra information about current node
target - node that is fired
res - stores the result
*/
Info calcTime(Node* node, Info& info, int target, int& res)
{
// Base case: if root is null
if (node == NULL) {
return info;
}
// If current node is leaf
if (node->left == NULL && node->right == NULL) {
// If current node is the first burnt node
if (node->data == target) {
info.contains = true;
info.time = 0;
}
return info;
}
// Information about left child of root
Info leftInfo;
calcTime(node->left, leftInfo, target, res);
// Information about right child of root
Info rightInfo;
calcTime(node->right, rightInfo, target, res);
// If left subtree contains the fired node then
// time required to reach fire to current node
// will be (1 + time required for left child)
info.time = (node->left && leftInfo.contains)
? (leftInfo.time + 1)
: -1;
// If right subtree contains the fired node then
// time required to reach fire to current node
// will be (1 + time required for right child)
if (info.time == -1)
info.time = (node->right && rightInfo.contains)
? (rightInfo.time + 1)
: -1;
// Storing(true or false) if the tree rooted at
// current node contains the fired node
info.contains
= ((node->left && leftInfo.contains)
|| (node->right && rightInfo.contains));
// Calculate the maximum depth of left subtree
info.lDepth
= !(node->left)
? 0
: (1 + max(leftInfo.lDepth, leftInfo.rDepth));
// Calculate the maximum depth of right subtree
info.rDepth
= !(node->right)
? 0
: (1
+ max(rightInfo.lDepth, rightInfo.rDepth));
// Calculating answer
if (info.contains) {
// If left subtree exists and
// it contains the fired node
if (node->left && leftInfo.contains) {
// calculate result
res = max(res, info.time + info.rDepth);
}
// If right subtree exists and it
// contains the fired node
if (node->right && rightInfo.contains) {
// calculate result
res = max(res, info.time + info.lDepth);
}
}
}
// Driver function to calculate minimum
// time required
int minTime(Node* root, int target)
{
int res = 0;
Info info;
calcTime(root, info, target, res);
return res;
}
// Driver Code
int main()
{
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->left->left->left = newNode(8);
root->left->right->left = newNode(9);
root->left->right->right = newNode(10);
root->left->right->left->left = newNode(11);
// target node is 8
int target = 11;
cout << minTime(root, target);
return 0;
}
Java
// Java program to find minimum time required
// to burn the binary tree completely
public class GFG {
// Tree Node
static class Node {
int data;
Node left, right;
Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
/*
***********ADDITIONAL INFO*************
lDepth - maximum height of left subtree
rDepth - maximum height of right subtree
contains - stores true if tree rooted at current node
contains the first burnt node
time - time to reach fire from the initially burnt leaf
node to this node
*/
static class Data {
int leftDepth, rightDepth, time;
boolean contains;
Data()
{
contains = false;
leftDepth = rightDepth = 0;
time = -1;
}
}
/*
Function to calculate time required to burn
tree completely
node - address of current node
info - extra information about current node
target - node that is fired
res - stores the result
*/
public static void getResult(Node node, Data data, int target)
{
// Base case: if root is null
if (node == null) {
return;
}
// If current node is leaf
if (node.left == null && node.right == null) {
// If current node is the first burnt node
if (node.data == target) {
data.contains = true;
data.time = 0;
}
return;
}
// Information about left child
Data leftData = new Data();
getResult(node.left, leftData, target);
// Information about right child
Data rightData = new Data();
getResult(node.right, rightData, target);
// If left subtree contains the fired node then
// time required to reach fire to current node
// will be (1 + time required for left child)
data.time = (leftData.contains) ? (leftData.time + 1) : -1;
// If right subtree contains the fired node then
// time required to reach fire to current node
// will be (1 + time required for right child)
if (data.time == -1)
data.time = (rightData.contains) ? (rightData.time + 1) : -1;
// Storing(true or false) if the tree rooted at
// current node contains the fired node
data.contains = (leftData.contains || rightData.contains);
// Calculate the maximum depth of left subtree
data.leftDepth = (node.left == null) ? 0 : (1 + Math.max(leftData.leftDepth, leftData.rightDepth));
// Calculate the maximum depth of right subtree
data.rightDepth = (node.right == null) ? 0 : (1 + Math.max(rightData.leftDepth, rightData.rightDepth));
// Calculating answer
if (data.contains) {
// If left subtree exists and
// it contains the fired node
if (leftData.contains) {
// calculate result
res = Math.max(res, data.time + data.rightDepth);
}
// If right subtree exists and it
// contains the fired node
if (rightData.contains) {
// calculate result
res = Math.max(res, data.time + data.leftDepth);
}
}
}
// To store the result
public static int res;
// Driver Code
public static void main(String args[])
{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.left.left.left = new Node(8);
root.left.right.left = new Node(9);
root.left.right.right = new Node(10);
root.left.right.left.left = new Node(11);
int target = 11;
res = 0;
getResult(root, new Data(), target);
System.out.println(res);
}
}
Python3
# Python program to find minimum time required # to burn the binary tree completely # Definition for a binary tree node class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None ''' ***********ADDITIONAL INFO************* lDepth - maximum height of left subtree rDepth - maximum height of right subtree contains - stores true if tree rooted at current node contains the first burnt node time - time to reach fire from the initially burnt leaf node to this node ''' class Info: def __init__(self): self.lDepth = 0 self.rDepth = 0 self.contains = False self.time = -1 class Solution: # Class Variable res = 0 ''' Function to calculate time required to burn tree completely node - address of current node info - extra information about current node target - node that is fired res - stores the result ''' def calcTime(self, node, info, target): # Base case: if root is null if node == None: return info if node.left == None and node.right == None: # If current node is the first burnt node if node.val == target: info.contains = True info.time = 0 return info # Information about left child of root leftInfo = Info() leftInfo = self.calcTime(node.left, leftInfo, target) # Information about right child of root rightInfo = Info() rightInfo = self.calcTime(node.right, rightInfo, target) # If left subtree contains the fired node then # time required to reach fire to current node # will be (1 + time required for left child) info.time = leftInfo.time + \ 1 if (node.left and leftInfo.contains) else -1 # If right subtree contains the fired node then # time required to reach fire to current node # will be (1 + time required for right child) if info.time == -1: info.time = rightInfo.time + \ 1 if (node.right and rightInfo.contains) else -1 # Storing(true or false) if the tree rooted at # current node contains the fired node info.contains = (node.left and leftInfo.contains) or ( node.right and rightInfo.contains) # Calculate the maximum depth of left subtree info.lDepth = 0 if (not node.left) else ( 1+max(leftInfo.lDepth, leftInfo.rDepth)) # Calculate the maximum depth of right subtree info.rDepth = 0 if (not node.right) else ( 1+max(rightInfo.lDepth, rightInfo.rDepth)) # Calculating answer if info.contains: # If left subtree exists and # it contains the fired node if node.left and leftInfo.contains: # calculate result self.res = max(self.res, info.time+info.rDepth) # If right subtree exists and it # contains the fired node if node.right and rightInfo.contains: # calculate result self.res = max(self.res, info.time+info.lDepth) return info # Driver function to calculate minimum # time required def solve(self, root, target): info = Info() self.calcTime(root, info, target) return self.res # Driver Code if __name__ == '__main__': # Construct tree shown in the above example 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.left.left.left = TreeNode(8) root.left.right.left = TreeNode(9) root.left.right.right = TreeNode(10) root.left.right.left.left = TreeNode(11) # Target Leaf Node target = 11 # Print min time to burn the complete tree s = Solution() print(s.solve(root, target)) # This code is contributed by Naman Taneja
C#
// C# program to find minimum time required
// to burn the binary tree completely
using System;
class GFG
{
// Tree Node
class Node
{
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
/*
***********ADDITIONAL INFO*************
lDepth - maximum height of left subtree
rDepth - maximum height of right subtree
contains - stores true if tree rooted at current node
contains the first burnt node
time - time to reach fire from the initially burnt leaf
node to this node
*/
class Data
{
public int leftDepth, rightDepth, time;
public bool contains;
public Data()
{
contains = false;
leftDepth = rightDepth = 0;
time = -1;
}
}
/*
Function to calculate time required to burn
tree completely
node - address of current node
info - extra information about current node
target - node that is fired
res - stores the result
*/
static void getResult(Node node, Data data,
int target)
{
// Base case: if root is null
if (node == null)
{
return;
}
// If current node is leaf
if (node.left == null &&
node.right == null)
{
// If current node is the first burnt node
if (node.data == target)
{
data.contains = true;
data.time = 0;
}
return;
}
// Information about left child
Data leftData = new Data();
getResult(node.left, leftData, target);
// Information about right child
Data rightData = new Data();
getResult(node.right, rightData, target);
// If left subtree contains the fired node then
// time required to reach fire to current node
// will be (1 + time required for left child)
data.time = (leftData.contains) ?
(leftData.time + 1) : -1;
// If right subtree contains the fired node then
// time required to reach fire to current node
// will be (1 + time required for right child)
if (data.time == -1)
data.time = (rightData.contains) ?
(rightData.time + 1) : -1;
// Storing(true or false) if the tree rooted at
// current node contains the fired node
data.contains = (leftData.contains ||
rightData.contains);
// Calculate the maximum depth of left subtree
data.leftDepth = (node.left == null) ?
0 : (1 + Math.Max(
leftData.leftDepth,
leftData.rightDepth));
// Calculate the maximum depth of right subtree
data.rightDepth = (node.right == null) ?
0 : (1 + Math.Max(
rightData.leftDepth,
rightData.rightDepth));
// Calculating answer
if (data.contains)
{
// If left subtree exists and
// it contains the fired node
if (leftData.contains)
{
// calculate result
res = Math.Max(res, data.time +
data.rightDepth);
}
// If right subtree exists and it
// contains the fired node
if (rightData.contains)
{
// calculate result
res = Math.Max(res, data.time +
data.leftDepth);
}
}
}
// To store the result
public static int res;
// Driver Code
public static void Main(String []args)
{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.left.left.left = new Node(8);
root.left.right.left = new Node(9);
root.left.right.right = new Node(10);
root.left.right.left.left = new Node(11);
int target = 11;
res = 0;
getResult(root, new Data(), target);
Console.WriteLine(res);
}
}
// This code is contributed by PrinciRaj1992
Producción
6
Otro enfoque : podemos relacionar este problema con la distancia mínima entre dos Nodes dados de un árbol binario . Lo único que cambia aquí es que tenemos que encontrar la distancia máxima entre el Node objetivo y los Nodes hoja.
algo:
1. Cree un hashmap y busque el Node para la asignación principal.
2. Cree punteros que apunten al Node que tiene un objetivo de valor.
3. Escriba una función que se llame recursivamente a sí misma y devuelva la distancia a todos los Nodes hoja.
4. Devolver la máxima distancia entre ellos.
C++
// C++ program to find minimum time required
// to burn the binary tree completely
#include <bits/stdc++.h>
using namespace std;
// Tree Node
struct Node {
int data;
Node* left;
Node* right;
Node()
{
left = NULL;
right = NULL;
}
};
// Utility function to create a new Node
Node* newNode(int val)
{
Node* temp = new Node;
temp->data = val;
return temp;
}
Node* n1=NULL;
/* Should return minimum distance between a and b
in a tree with given root*/
void getparent(Node* root,Node* parent , map<Node* , Node*> &map)
{
if(root == NULL)
return ;
map[root] = parent;
getparent(root->left,root,map);
getparent(root->right,root,map);
return;
}
void getnode(Node* root,int a)
{
if(root == NULL)
return ;
if(root->data == a)
n1 = root;
getnode(root->left,a);
getnode(root->right,a);
return;
}
int getmaxdis(Node* target,int dis,map<Node* , int> vis,map<Node* , Node*> &map)
{
if(target == NULL)
return dis - 1;
if(vis.find(target) != vis.end())
return INT_MIN;
// calls
// calls
vis[target] = 1;
int a1 = INT_MIN;
int a2 = INT_MIN;
int a3 = INT_MIN;
// if(a->left!=NULL)
a1 = getmaxdis(target->left,dis + 1,vis,map); // left child
// if(a->right!=NULL)
a2 = getmaxdis(target->right,dis + 1,vis,map); // right child
// if(map[a] != NULL)
a3 = getmaxdis(map[target],dis + 1,vis,map); // parent
return max(max(a1,a2),a3);
}
int minTime(Node* root, int target)
{
map<Node* , Node*> par;
getparent(root,NULL,par);
getnode(root,target);
map<Node*,int> vis;
return getmaxdis(n1,0,vis,par);
}
// Driver Code
int main()
{
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->left->left->left = newNode(8);
root->left->right->left = newNode(9);
root->left->right->right = newNode(10);
root->left->right->left->left = newNode(11);
// target node is 8
int target = 11;
cout << minTime(root, target);
return 0;
}
//This code is contributed by Arpit Jain
Producción
6
Complejidad de tiempo : O (n) ya que estamos atravesando el árbol en las tres direcciones desde el Node de destino.
Espacio auxiliar : O (n) ya que estamos almacenando el padre de cada Node.
Publicación traducida automáticamente
Artículo escrito por harsh.agarwal0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA