Dado un árbol binario , la tarea de cada nivel L es imprimir el Node L del árbol. Si el L -ésimo Node no está presente para ningún nivel, imprima -1 .
Nota: Considere que el Node raíz está en el nivel 1 del árbol binario.
Ejemplos:
Entrada: A continuación se muestra el Árbol dado: Salida: Nivel 1: 1 Nivel 2: 3 Nivel 3: 6 Nivel 4: 11 Explicación: Para el primer nivel, el primer Node es 1. Para el segundo nivel, el segundo Node es 3. Para el tercer nivel, el 3er Node es 6. Para el cuarto nivel, el 4to Node es 11.
Entrada: A continuación se muestra el árbol dado: Salida: Nivel 1: 1 Nivel 2: 3 Nivel 3: 6 Nivel 4: -1 Explicación: Para el primer nivel, el primer Node es 1. Para el segundo nivel, el segundo Node es 3 Para el tercer nivel, el 3er Node es 6. Para el cuarto nivel, el 4to Node no está disponible. Por lo tanto, imprima -1.
Planteamiento: Para solucionar este problema la idea es utilizar Multimap . Siga los pasos a continuación para resolver el problema:
- Atraviese el árbol dado y almacene el nivel de cada Node y el valor del Node en el Multimapa .
- Los niveles de los Nodes se consideran como la clave del multimapa. Lleve un registro del nivel máximo del árbol binario (digamos L ).
- Ahora, itere el mapa múltiple sobre el rango [1, L] y realice las siguientes operaciones:
- Para cada nivel L , recorra hasta el L -ésimo Node de ese nivel, verifique si existe o no. Si se encuentra que existe, imprime el valor de ese Node.
- De lo contrario, imprima «-1» y continúe con el siguiente nivel.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the level of the node and
// its value at the max level of BT
multimap<int, int> m;
// Stores the maximum level
int maxlevel = 0;
// Structure of Binary Tree
struct node {
int data;
struct node* left;
struct node* right;
};
// Function to insert the node in
// the Binary Tree
struct node* newnode(int d)
{
struct node* temp
= (struct node*)malloc(
sizeof(struct node));
temp->data = d;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// Function to find node of Nth level
void findNode(struct node* root, int level)
{
// If root exists
if (root) {
// Traverse left subtree
findNode(root->left, level + 1);
// Insert the node's level and
// its value into the multimap
m.insert({ level, root->data });
// Update the maximum level
maxlevel = max(maxlevel, level);
// Traverse the right subtree
findNode(root->right, level + 1);
}
}
// Function to print the L-th node at
// L-th level of the Binary Tree
void printNode(struct node* root, int level)
{
// Function Call
findNode(root, level);
// Iterator for traversing map
multimap<int, int>::iterator it;
// Iterate all the levels
for (int i = 0; i <= maxlevel; i++) {
// Print the current level
cout << "Level " << i + 1 << ": ";
it = m.find(i);
int flag = 0;
// Iterate upto i-th node of the
// i-th level
for (int j = 0; j < i; j++) {
it++;
// If end of the level
// is reached
if (it == m.end()) {
flag = 1;
break;
}
}
// If i-th node does not exist
// in the i-th level
if (flag == 1 || it->first != i) {
cout << "-1" << endl;
}
// Otherwise
else {
// Print the i-th node
cout << it->second << endl;
}
}
}
// Driver code
int main()
{
// Construct the Binary Tree
struct node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->left->right->left = newnode(11);
root->left->right->right = newnode(12);
root->left->left->left = newnode(9);
root->left->left->right = newnode(10);
root->right->left = newnode(6);
root->right->right = newnode(7);
root->right->right->left = newnode(13);
root->right->right->right = newnode(14);
// Function Call
printNode(root, 0);
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Stores the level of the node and
// its value at the max level of BT
static HashMap<Integer,ArrayList<Integer>> m = new HashMap<>();
// Stores the maximum level
static int maxlevel = 0;
// Structure of a BST node
static class node {
int data;
node left;
node right;
}
// Utility function to create a new BST node
static node newnode(int d)
{
node temp = new node();
temp.left = null;
temp.right = null;
temp.data = d;
return temp;
}
// Function to find node of Nth level
static void findNode(node root, int level)
{
// If root exists
if (root!=null) {
// Traverse left subtree
findNode(root.left, level + 1);
// Insert the node's level and
// its value into the multimap
if(m.get(level)==null){
m.put(level,new ArrayList<Integer>());
}
m.get(level).add(root.data);
// Update the maximum level
maxlevel = Math.max(maxlevel, level);
// Traverse the right subtree
findNode(root.right, level + 1);
}
}
// Function to print the L-th node at
// L-th level of the Binary Tree
static void printNode(node root, int level)
{
// Function Call
findNode(root, level);
// Iterate all the levels
for (int i = 0; i <= maxlevel; i++) {
// Print the current level
System.out.print("Level " + (i + 1) + ": ");
List<Integer> it = m.get(i);
int flag = 0;
// Iterate upto i-th node of the
// i-th level
if(it.size()<i){
// If end of the level
// is reached
flag=1;
System.out.print("-1\n");
}else{
// Print the i-th node
System.out.print(it.get(i)+"\n");
}
}
}
//Driver Code
public static void main (String[] args) {
// Construct the Binary Tree
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
root.left.right.left = newnode(11);
root.left.right.right = newnode(12);
root.left.left.left = newnode(9);
root.left.left.right = newnode(10);
root.right.left = newnode(6);
root.right.right = newnode(7);
root.right.right.left = newnode(13);
root.right.right.right = newnode(14);
// Function Call
printNode(root, 0);
}
}
// This code is contributed by shruti456rawal
Level 1: 1 Level 2: 3 Level 3: 6 Level 4: 12
Complejidad de Tiempo: O(N), donde N es el número de Nodes en el Árbol Binario.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sunilkannur98 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA