Dado un árbol binario y un Node de destino. Al dar el fuego al Node de destino y el fuego comienza a extenderse en un árbol completo. La tarea es imprimir la secuencia de los Nodes en llamas de un árbol binario.
Reglas para quemar los Nodes:
- El fuego se propagará constantemente solo a los Nodes conectados.
- Cada Node tarda el mismo tiempo en quemarse.
- Un Node se quema solo una vez.
Ejemplos:
Input :
12
/ \
13 10
/ \
14 15
/ \ / \
21 24 22 23
target node = 14
Output :
14
21, 24, 10
15, 12
22, 23, 13
Explanation : First node 14 burns then it gives fire to it's
neighbors(21, 24, 10) and so on. This process continues until
the whole tree burns.
Input :
12
/ \
19 82
/ / \
41 15 95
\ / / \
2 21 7 16
target node = 41
Output :
41
2, 19
12
82
15, 95
21, 7, 16
Enfoque:
Primero busque el Node de destino en un árbol binario recursivamente . Después de encontrar el Node de destino, imprímalo y guarde su hijo izquierdo (si existe) y su hijo derecho (si existe) en una cola. y volver. Ahora, obtenga el tamaño de la cola y ejecute el ciclo while. Imprimir elementos en la cola.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation to print the sequence
// of burning of nodes of a binary tree
#include <bits/stdc++.h>
using namespace std;
// A Tree node
struct Node {
int key;
struct Node *left, *right;
};
// Utility function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Utility function to print the sequence of burning nodes
int burnTreeUtil(Node* root, int target, queue<Node*>& q)
{
// Base condition
if (root == NULL) {
return 0;
}
// Condition to check whether target
// node is found or not in a tree
if (root->key == target) {
cout << root->key << endl;
if (root->left != NULL) {
q.push(root->left);
}
if (root->right != NULL) {
q.push(root->right);
}
// Return statements to prevent
// further function calls
return 1;
}
int a = burnTreeUtil(root->left, target, q);
if (a == 1) {
int qsize = q.size();
// Run while loop until size of queue
// becomes zero
while (qsize--) {
Node* temp = q.front();
// Printing of burning nodes
cout << temp->key << " , ";
q.pop();
// Check if condition for left subtree
if (temp->left != NULL)
q.push(temp->left);
// Check if condition for right subtree
if (temp->right != NULL)
q.push(temp->right);
}
if (root->right != NULL)
q.push(root->right);
cout << root->key << endl;
// Return statement it prevents further
// further function call
return 1;
}
int b = burnTreeUtil(root->right, target, q);
if (b == 1) {
int qsize = q.size();
// Run while loop until size of queue
// becomes zero
while (qsize--) {
Node* temp = q.front();
// Printing of burning nodes
cout << temp->key << " , ";
q.pop();
// Check if condition for left subtree
if (temp->left != NULL)
q.push(temp->left);
// Check if condition for left subtree
if (temp->right != NULL)
q.push(temp->right);
}
if (root->left != NULL)
q.push(root->left);
cout << root->key << endl;
// Return statement it prevents further
// further function call
return 1;
}
}
// Function will print the sequence of burning nodes
void burnTree(Node* root, int target)
{
queue<Node*> q;
// Function call
burnTreeUtil(root, target, q);
// While loop runs unless queue becomes empty
while (!q.empty()) {
int qSize = q.size();
while (qSize > 0) {
Node* temp = q.front();
// Printing of burning nodes
cout << temp->key;
// Insert left child in a queue, if exist
if (temp->left != NULL) {
q.push(temp->left);
}
// Insert right child in a queue, if exist
if (temp->right != NULL) {
q.push(temp->right);
}
if (q.size() != 1)
cout << " , ";
q.pop();
qSize--;
}
cout << endl;
}
}
// Driver Code
int main()
{
/* 10
/ \
12 13
/ \
14 15
/ \ / \
21 22 23 24
Let us create Binary Tree as shown
above */
Node* root = newNode(10);
root->left = newNode(12);
root->right = newNode(13);
root->right->left = newNode(14);
root->right->right = newNode(15);
root->right->left->left = newNode(21);
root->right->left->right = newNode(22);
root->right->right->left = newNode(23);
root->right->right->right = newNode(24);
int targetNode = 14;
// Function call
burnTree(root, targetNode);
return 0;
}
Java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
// Tree node class
class TreeNode
{
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right)
{
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
// function to print the sequence of burning nodes
public static int search(TreeNode root,
int num,
Map<Integer,
Set<Integer> > levelOrderMap)
{
if (root != null)
{
// Condition to check whether target
// node is found or not in a tree
if (root.val == num)
{
levelOrderStoredInMap(root.left, 1,
levelOrderMap);
levelOrderStoredInMap(root.right, 1,
levelOrderMap);
// Return statements to prevent
// further function calls
return 1;
}
int k = search(root.left, num, levelOrderMap);
if (k > 0)
{
// store root in map with k
storeRootAtK(root, k, levelOrderMap);
// store level order for other branch
levelOrderStoredInMap(root.right, k + 1,
levelOrderMap);
return k + 1;
}
k = search(root.right, num, levelOrderMap);
if (k > 0)
{
// store root in map with k
storeRootAtK(root, k, levelOrderMap);
// store level order for other branch
levelOrderStoredInMap(root.left, k + 1,
levelOrderMap);
return k + 1;
}
}
return -1; // Base condition
}
public static void levelOrderStoredInMap(
TreeNode root, int k,
Map<Integer, Set<Integer> > levelOrderMap)
{
if (root != null) {
storeRootAtK(root, k, levelOrderMap);
levelOrderStoredInMap(root.left, k + 1,
levelOrderMap);
levelOrderStoredInMap(root.right, k + 1,
levelOrderMap);
}
}
private static void
storeRootAtK(TreeNode root, int k,
Map<Integer, Set<Integer> > levelOrderMap)
{
if (levelOrderMap.containsKey(k)) {
levelOrderMap.get(k).add(root.val);
}
else {
Set<Integer> set = new HashSet<>();
set.add(root.val);
levelOrderMap.put(k, set);
}
}
// Driver Code
public static void main(String[] args)
{
/* 12
/ \
13 10
/ \
14 15
/ \ / \
21 24 22 23
Let us create Binary Tree as shown
above */
TreeNode root = new TreeNode(12);
root.left = new TreeNode(13);
root.right = new TreeNode(10);
root.right.left = new TreeNode(14);
root.right.right = new TreeNode(15);
TreeNode left = root.right.left;
TreeNode right = root.right.right;
left.left = new TreeNode(21);
left.right = new TreeNode(24);
right.left = new TreeNode(22);
right.right = new TreeNode(23);
// Utility map to store the sequence of burning
// nodes
Map<Integer, Set<Integer> > levelOrderMap
= new HashMap<>();
// search node and store the level order from that
// node in map
search(root, 14, levelOrderMap);
// will print the sequence of burning nodes
System.out.println(14);
for (Integer level : levelOrderMap.keySet())
{
for (Integer val : levelOrderMap.get(level))
{
System.out.print(val + " ");
}
System.out.println();
}
}
}
// This code is contributed by Niharika Sahai
Producción
14 21 , 22 , 13 15 , 10 23 , 24 , 12
Otro enfoque: convierta el árbol en un gráfico no dirigido e imprima su recorrido de orden de nivel
- Cree un gráfico no dirigido usando Treenodes como vértices y la relación padre-hijo como bordes
- Haz BFS con el vértice de origen como destino.
Java
import java.io.*;
import java.util.*;
public class GFG {
/*package whatever //do not write package name here */
static class TreeNode
{
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right)
{
this.val = val;
this.left = left;
this.right = right;
}
}
static Map<TreeNode, List<TreeNode>> map = new HashMap<>();
public static void main (String[] args) {
TreeNode root = new TreeNode(12);
root.left = new TreeNode(13);
root.right = new TreeNode(10);
root.right.left = new TreeNode(14);
root.right.right = new TreeNode(15);
TreeNode left = root.right.left;
TreeNode right = root.right.right;
left.left = new TreeNode(21);
left.right = new TreeNode(24);
right.left = new TreeNode(22);
right.right = new TreeNode(23);
// target Node value is 14
burnTree(root,left);
System.out.println();
}
private static void burnTree(TreeNode root, TreeNode target) {
List<Integer> res = new ArrayList<Integer> ();
if (root == null )
return ;
buildMap(root, null);
if (!map.containsKey(target))
{ System.out.println("Target Not found");
return;
}
Set<TreeNode> visited = new HashSet<TreeNode>();
//BFS traversal
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(target);
visited.add(target);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
System.out.print(node.val+" ");
for (TreeNode next : map.get(node)) {
if (visited.contains(next))
continue;
visited.add(next);
q.add(next);
}
}
System.out.println();
}
}
// build undirected graph
private static void buildMap(TreeNode node, TreeNode parent) {
if (node == null)
return;
if (!map.containsKey(node)) {
map.put(node, new ArrayList<TreeNode>());
if (parent != null) { map.get(node).add(parent); map.get(parent).add(node) ; }
buildMap(node.left, node);
buildMap(node.right, node);
}
}
}
C#
//C# program to print the sequence
// of burning of nodes of a binary tree
using System;
using System.Collections.Generic;
using System.Linq;
public class GFG{
// Tree node class
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
TreeNode() {}
public TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right)
{
this.val = val;
this.left = left;
this.right = right;
}
}
static Dictionary <TreeNode, List<TreeNode>> map = new Dictionary <TreeNode, List<TreeNode>>();
static public void Main (){
TreeNode root = new TreeNode(12);
root.left = new TreeNode(13);
root.right = new TreeNode(10);
root.right.left = new TreeNode(14);
root.right.right = new TreeNode(15);
TreeNode left = root.right.left;
TreeNode right = root.right.right;
left.left = new TreeNode(21);
left.right = new TreeNode(24);
right.left = new TreeNode(22);
right.right = new TreeNode(23);
// target Node value is 14
burnTree(root,left);
Console.Write("\n");
}
static public void burnTree(TreeNode root, TreeNode target){
//List<int> res = new List<int> ();
if (root == null )
return ;
buildMap(root, null);
if (!map.ContainsKey(target))
{
Console.Write("Target Not found");
return;
}
HashSet<TreeNode> visited = new HashSet<TreeNode>();
//BFS traversal
Queue<TreeNode> q = new Queue<TreeNode>();
q.Enqueue(target);
visited.Add(target);
while (q.Count()!=0) {
int size = q.Count();
for (int i = 0; i < size; i++) {
TreeNode node = q.Dequeue();
Console.Write(node.val+" ");
foreach (TreeNode next in map[node]) {
if (visited.Contains(next))
continue;
visited.Add(next);
q.Enqueue(next);
}
}
Console.Write("\n");
}
}
// build undirected graph
static public void buildMap(TreeNode node, TreeNode parent){
if (node == null)
return;
if (!map.ContainsKey(node)){
map[node] = new List<TreeNode>();
if (parent != null){
map[node].Add(parent);
map[parent].Add(node);
}
buildMap(node.left, node);
buildMap(node.right, node);
}
}
}
// This code is contributed by shruti456rawal
Producción
14 10 21 24 12 15 13 22 23
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA