Dado un Árbol Binario y un entero K , la tarea es encontrar el nivel del Árbol Binario con ancho K . Si existen múltiples niveles con ancho K , imprima el nivel más bajo. Si no existe tal nivel, imprima -1 .
El ancho de un nivel de un árbol binario se define como el número de Nodes entre el Node más a la izquierda y el más a la derecha en ese nivel, incluidos los Nodes NULL entre ellos también.
Ejemplos:
Entrada: K = 4
5 --------- 1st level width = 1 => (5) / \ 6 2 -------- 2nd level width = 2 => (6, 2) / \ \ 7 3 8 -------3rd level width = 4 => (7, 3, NULL, 8) / \ 5 4 -----------4th level width = 4 => (5, NULL, NULL, 4)Salida: 3
Explicación:
Para el árbol dado, los niveles que tienen ancho K ( = 4) son 3 y 4.
Ya que 3 es el mínimo de los dos, imprima el mínimo.Entrada: K = 7
1 --------- 1st level width = 1 => (1) / \ 2 9 -------- 2nd level width = 2 => (2, 9) / \ 7 8 ---------3rd level width = 4 => (7, NULL, NULL, 8) / / 5 9 -----------4th level width = 7 => (5, NULL, NULL, / NULL, NULL, NULL, 9) 2 -----------5th level width = 1 => (2) / 1 -----------6th level width = 1 => (1)Salida: 4
Explicación:
Para el árbol dado, el nivel que tiene ancho K ( = 7) es 4.
Enfoque:
La idea básica para resolver el problema es agregar una etiqueta a cada Node. Si un padre tiene una etiqueta i , entonces asigne una etiqueta 2*i a su hijo izquierdo y 2*i+1 a su hijo derecho. Esto ayudará a incluir los Nodes NULL en el cálculo.
Siga los pasos a continuación:
- Realice el cruce de orden de nivel en el árbol dado usando una cola .
- La cola contiene un par de {Node, Etiqueta}. Inicialmente inserte { rootNode, 0 } en la cola.
- Si el padre tiene la etiqueta i, entonces para un hijo izquierdo, inserte { hijo izquierdo , 2 * i } en la cola y para el hijo derecho, inserte { hijo derecho , 2 * i + 1 } en la cola.
- Para cada nivel, asuma a como etiqueta del Node más a la izquierda y b como etiqueta del Node más a la derecha, luego (b-a+1) da el ancho de ese nivel.
- Compruebe si el ancho es igual a K . Si es así, devuelve el nivel .
- Si ninguno de los niveles tiene ancho K , devuelva -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a Tree node
struct Node {
int key;
struct Node *left, *right;
};
// Utility function to create
// and initialize a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Function returns required level
// of width k, if found else -1
int findLevel(Node* root,
int k, int level)
{
// To store the node and the label
// and perform traversal
queue<pair<Node*, int> > qt;
qt.push(make_pair(root, 0));
int count = 1, b, a = 0;
while (!qt.empty()) {
pair<Node*, int> temp = qt.front();
qt.pop();
// Taking the last label
// of each level of the tree
if (count == 1) {
b = temp.second;
}
if ((temp.first)->left) {
qt.push(make_pair(
temp.first->left,
2 * temp.second));
}
if (temp.first->right) {
qt.push(make_pair(
temp.first->right,
2 * temp.second + 1));
}
count--;
// Check width of current level
if (count == 0) {
// If the width is equal to k
// then return that level
if (b - a + 1 == k)
return level;
pair<Node*, int> secondLabel = qt.front();
// Taking the first label
// of each level of the tree
a = secondLabel.second;
level += 1;
count = qt.size();
}
}
// If any level does not has
// width equal to k, return -1
return -1;
}
// Driver Code
int main()
{
Node* root = newNode(5);
root->left = newNode(6);
root->right = newNode(2);
root->right->right = newNode(8);
root->left->left = newNode(7);
root->left->left->left = newNode(5);
root->left->right = newNode(3);
root->left->right->right = newNode(4);
int k = 4;
cout << findLevel(root, k, 1) << endl;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Structure of
// binary tree node
static class Node
{
int data;
Node left, right;
};
static class pair
{
Node first;
int second;
pair(Node first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to create new node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function returns required level
// of width k, if found else -1
static int findLevel(Node root,
int k, int level)
{
// To store the node and the label
// and perform traversal
Queue<pair> qt = new LinkedList<>();
qt.add(new pair(root, 0));
int count = 1, b = 0, a = 0;
while (!qt.isEmpty())
{
pair temp = qt.peek();
qt.poll();
// Taking the last label
// of each level of the tree
if (count == 1)
{
b = temp.second;
}
if (temp.first.left != null)
{
qt.add(new pair(
temp.first.left,
2 * temp.second));
}
if (temp.first.right != null)
{
qt.add(new pair(
temp.first.right,
2 * temp.second + 1));
}
count--;
// Check width of current level
if (count == 0)
{
// If the width is equal to k
// then return that level
if ((b - a + 1) == k)
return level;
pair secondLabel = qt.peek();
// Taking the first label
// of each level of the tree
a = secondLabel.second;
level += 1;
count = qt.size();
}
}
// If any level does not has
// width equal to k, return -1
return -1;
}
// Driver code
public static void main(String[] args)
{
Node root = newNode(5);
root.left = newNode(6);
root.right = newNode(2);
root.right.right = newNode(8);
root.left.left = newNode(7);
root.left.left.left = newNode(5);
root.left.right = newNode(3);
root.left.right.right = newNode(4);
int k = 4;
System.out.println(findLevel(root, k, 1));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach from collections import deque # Structure of a Tree node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function returns required level # of width k, if found else -1 def findLevel(root: Node, k: int, level: int) -> int: # To store the node and the label # and perform traversal qt = deque() qt.append([root, 0]) count = 1 b = 0 a = 0 while qt: temp = qt.popleft() # Taking the last label # of each level of the tree if (count == 1): b = temp[1] if (temp[0].left): qt.append([temp[0].left, 2 * temp[1]]) if (temp[0].right): qt.append([temp[0].right, 2 * temp[1] + 1]) count -= 1 # Check width of current level if (count == 0): # If the width is equal to k # then return that level if (b - a + 1 == k): return level secondLabel = qt[0] # Taking the first label # of each level of the tree a = secondLabel[1] level += 1 count = len(qt) # If any level does not has # width equal to k, return -1 return -1 # Driver Code if __name__ == "__main__": root = Node(5) root.left = Node(6) root.right = Node(2) root.right.right = Node(8) root.left.left = Node(7) root.left.left.left = Node(5) root.left.right = Node(3) root.left.right.right = Node(4) k = 4 print(findLevel(root, k, 1)) # This code is contributed by sanjeev2552
C#
// C# program to implement
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Structure of
// binary tree node
class Node
{
public int data;
public Node left, right;
};
class pair
{
public Node first;
public int second;
public pair(Node first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to create new node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function returns required level
// of width k, if found else -1
static int findLevel(Node root,
int k, int level)
{
// To store the node and the label
// and perform traversal
Queue qt = new Queue();
qt.Enqueue(new pair(root, 0));
int count = 1, b = 0, a = 0;
while (qt.Count!=0)
{
pair temp = (pair)qt.Dequeue();
// Taking the last label
// of each level of the tree
if (count == 1)
{
b = temp.second;
}
if (temp.first.left != null)
{
qt.Enqueue(new pair(
temp.first.left,
2 * temp.second));
}
if (temp.first.right != null)
{
qt.Enqueue(new pair(
temp.first.right,
2 * temp.second + 1));
}
count--;
// Check width of current level
if (count == 0)
{
// If the width is equal to k
// then return that level
if ((b - a + 1) == k)
return level;
pair secondLabel = (pair)qt.Peek();
// Taking the first label
// of each level of the tree
a = secondLabel.second;
level += 1;
count = qt.Count;
}
}
// If any level does not has
// width equal to k, return -1
return -1;
}
// Driver code
public static void Main(string[] args)
{
Node root = newNode(5);
root.left = newNode(6);
root.right = newNode(2);
root.right.right = newNode(8);
root.left.left = newNode(7);
root.left.left.left = newNode(5);
root.left.right = newNode(3);
root.left.right.right = newNode(4);
int k = 4;
Console.Write(findLevel(root, k, 1));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to implement
// the above approach
// Structure of
// binary tree node
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
class pair
{
constructor(first, second)
{
this.first = first;
this.second = second;
}
}
// Function to create new node
function newNode(data)
{
var temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function returns required level
// of width k, if found else -1
function findLevel(root, k, level)
{
// To store the node and the label
// and perform traversal
var qt = [];
qt.push(new pair(root, 0));
var count = 1, b = 0, a = 0;
while (qt.length!=0)
{
var temp = qt.shift();
// Taking the last label
// of each level of the tree
if (count == 1)
{
b = temp.second;
}
if (temp.first.left != null)
{
qt.push(new pair(
temp.first.left,
2 * temp.second));
}
if (temp.first.right != null)
{
qt.push(new pair(
temp.first.right,
2 * temp.second + 1));
}
count--;
// Check width of current level
if (count == 0)
{
// If the width is equal to k
// then return that level
if ((b - a + 1) == k)
return level;
var secondLabel = qt[0];
// Taking the first label
// of each level of the tree
a = secondLabel.second;
level += 1;
count = qt.length;
}
}
// If any level does not has
// width equal to k, return -1
return -1;
}
// Driver code
var root = newNode(5);
root.left = newNode(6);
root.right = newNode(2);
root.right.right = newNode(8);
root.left.left = newNode(7);
root.left.left.left = newNode(5);
root.left.right = newNode(3);
root.left.right.right = newNode(4);
var k = 4;
document.write(findLevel(root, k, 1));
</script>
Producción:
3
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)