Dado un árbol binario que consta de N Nodes, la tarea es encontrar el ancho máximo del árbol dado, donde el ancho máximo se define como el máximo de todos los anchos en cada nivel del árbol dado.
El ancho de un árbol para cualquier nivel se define como el número de Nodes entre los dos Nodes extremos de ese nivel, incluido el Node NULL en el medio.
Ejemplos:
Entrada:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
Salida: 4
Explicación:
El ancho del nivel 1 es 1
El ancho del nivel 2 es 2
El ancho del nivel 3 es 4 (porque tiene un Node nulo entre 5 y 8)
El ancho del nivel 4 es 2Por lo tanto, el ancho máximo del árbol es el máximo de todos los anchos, es decir, max{1, 2, 4, 2} = 4.
Entrada:
1
/
2
/
3
Salida: 1
Enfoque: el problema dado se puede resolver representando el árbol binario como la representación de array del montón . Supongamos que el índice de un Node es i , entonces los índices de sus hijos son (2*i + 1) y (2*i + 2) . Ahora, para cada nivel, encuentre la posición del Node más a la izquierda y el Node más a la derecha en cada nivel, luego la diferencia entre ellos dará el ancho de ese nivel. Siga los pasos a continuación para resolver este problema:
- Inicialice dos HashMap , digamos HMMax y HMMin que almacenan la posición del Node más a la izquierda y el Node más a la derecha en cada nivel
- Cree una función recursiva getMaxWidthHelper(root, lvl, i) que tome la raíz del árbol, el nivel inicial del árbol inicialmente 0 y la posición del Node raíz del árbol inicialmente 0 y realice los siguientes pasos:
- Si la raíz del árbol es NULL , entonces regresa.
- Almacene el índice del Node más a la izquierda en el nivel lvl en el HMMin .
- Almacene el índice del Node más a la derecha en el nivel lvl en el HMMax .
- Llame recursivamente al subárbol izquierdo actualizando el valor de lvl a lvl + 1 y i a (2*i + 1) .
- Llame recursivamente al subárbol derecho actualizando el valor de lvl a lvl + 1 y i a (2*i + 2) .
- Llame a la función getMaxWidthHelper(root, 0, 0) para llenar el HashMap.
- Después de completar los pasos anteriores, imprima el valor máximo de (HMMax(L) – HMMin(L) + 1) entre todos los valores posibles del nivel L.
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;
// Tree Node structure
struct Node
{
int data;
Node *left, *right;
// Constructor
Node(int item)
{
data = item;
left = right = NULL;
}
};
Node *root;
int maxx = 0;
// Stores the position of leftmost
// and rightmost node in each level
map<int, int> hm_min;
map<int, int> hm_max;
// Function to store the min and the
// max index of each nodes in hashmaps
void getMaxWidthHelper(Node *node,
int lvl, int i)
{
// Base Case
if (node == NULL)
{
return;
}
// Stores rightmost node index
// in the hm_max
if (hm_max[lvl])
{
hm_max[lvl] = max(i, hm_max[lvl]);
}
else
{
hm_max[lvl] = i;
}
// Stores leftmost node index
// in the hm_min
if (hm_min[lvl])
{
hm_min[lvl] = min(i, hm_min[lvl]);
}
// Otherwise
else
{
hm_min[lvl] = i;
}
// If the left child of the node
// is not empty, traverse next
// level with index = 2*i + 1
getMaxWidthHelper(node->left, lvl + 1,
2 * i + 1);
// If the right child of the node
// is not empty, traverse next
// level with index = 2*i + 2
getMaxWidthHelper(node->right, lvl + 1,
2 * i + 2);
}
// Function to find the maximum
// width of the tree
int getMaxWidth(Node *root)
{
// Helper function to fill
// the hashmaps
getMaxWidthHelper(root, 0, 0);
// Traverse to each level and
// find the maximum width
for(auto lvl : hm_max)
{
maxx = max(maxx, hm_max[lvl.first] -
hm_min[lvl.first] + 1);
}
// Return the result
return maxx;
}
// Driver Code
int main()
{
/*
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
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->right = new Node(8);
root->right->right->left = new Node(6);
root->right->right->right = new Node(7);
// Function Call
cout << (getMaxWidth(root));
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.util.*;
// Tree Node structure
class Node {
int data;
Node left, right;
// Constructor
Node(int item)
{
data = item;
left = right = null;
}
}
// Driver Code
public class Main {
Node root;
int maxx = 0;
// Stores the position of leftmost
// and rightmost node in each level
HashMap<Integer, Integer> hm_min
= new HashMap<>();
HashMap<Integer, Integer> hm_max
= new HashMap<>();
// Function to store the min and the
// max index of each nodes in hashmaps
void getMaxWidthHelper(Node node,
int lvl, int i)
{
// Base Case
if (node == null) {
return;
}
// Stores rightmost node index
// in the hm_max
if (hm_max.containsKey(lvl)) {
hm_max.put(lvl,
Math.max(
i, hm_max.get(lvl)));
}
else {
hm_max.put(lvl, i);
}
// Stores leftmost node index
// in the hm_min
if (hm_min.containsKey(lvl)) {
hm_min.put(lvl,
Math.min(
i, hm_min.get(lvl)));
}
// Otherwise
else {
hm_min.put(lvl, i);
}
// If the left child of the node
// is not empty, traverse next
// level with index = 2*i + 1
getMaxWidthHelper(node.left, lvl + 1,
2 * i + 1);
// If the right child of the node
// is not empty, traverse next
// level with index = 2*i + 2
getMaxWidthHelper(node.right, lvl + 1,
2 * i + 2);
}
// Function to find the maximum
// width of the tree
int getMaxWidth(Node root)
{
// Helper function to fill
// the hashmaps
getMaxWidthHelper(root, 0, 0);
// Traverse to each level and
// find the maximum width
for (Integer lvl : hm_max.keySet()) {
maxx
= Math.max(
maxx,
hm_max.get(lvl)
- hm_min.get(lvl) + 1);
}
// Return the result
return maxx;
}
// Driver Code
public static void main(String args[])
{
Main tree = new Main();
/*
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(8);
tree.root.right.right.left = new Node(6);
tree.root.right.right.right = new Node(7);
// Function Call
System.out.println(
tree.getMaxWidth(
tree.root));
}
}
Python3
# Python3 program for the above approach
# Tree Node structure
class Node:
def __init__(self, item):
self.data = item
self.left = None
self.right = None
maxx = 0
# Stores the position of leftmost
# and rightmost node in each level
hm_min = {}
hm_max = {}
# Function to store the min and the
# max index of each nodes in hashmaps
def getMaxWidthHelper(node, lvl, i):
# Base Case
if (node == None):
return
# Stores rightmost node index
# in the hm_max
if (lvl in hm_max):
hm_max[lvl] = max(i, hm_max[lvl])
else:
hm_max[lvl] = i
# Stores leftmost node index
# in the hm_min
if (lvl in hm_min):
hm_min[lvl] = min(i, hm_min[lvl])
# Otherwise
else:
hm_min[lvl] = i
# If the left child of the node
# is not empty, traverse next
# level with index = 2*i + 1
getMaxWidthHelper(node.left, lvl + 1, 2 * i + 1)
# If the right child of the node
# is not empty, traverse next
# level with index = 2*i + 2
getMaxWidthHelper(node.right, lvl + 1, 2 * i + 2)
# Function to find the maximum
# width of the tree
def getMaxWidth(root):
global maxx
# Helper function to fill
# the hashmaps
getMaxWidthHelper(root, 0, 0)
# Traverse to each level and
# find the maximum width
for lvl in hm_max.keys():
maxx = max(maxx, hm_max[lvl] - hm_min[lvl] + 1)
# Return the result
return maxx
"""
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
"""
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(8)
root.right.right.left = Node(6)
root.right.right.right = Node(7)
# Function Call
print(getMaxWidth(root))
# This code is contributed by decode2207.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// A Binary Tree Node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int item)
{
data = item;
left = right = null;
}
};
static int maxx = 0;
// Stores the position of leftmost
// and rightmost node in each level
static Dictionary<int, int> hm_min = new Dictionary<int, int>();
static Dictionary<int, int> hm_max = new Dictionary<int, int>();
// Function to store the min and the
// max index of each nodes in hashmaps
static void getMaxWidthHelper(Node node,
int lvl, int i)
{
// Base Case
if (node == null) {
return;
}
// Stores rightmost node index
// in the hm_max
if (hm_max.ContainsKey(lvl)) {
hm_max[lvl] = Math.Max(i, hm_max[lvl]);
}
else {
hm_max[lvl] = i;
}
// Stores leftmost node index
// in the hm_min
if (hm_min.ContainsKey(lvl)) {
hm_min[lvl] = Math.Min(i, hm_min[lvl]);
}
// Otherwise
else {
hm_min[lvl] = i;
}
// If the left child of the node
// is not empty, traverse next
// level with index = 2*i + 1
getMaxWidthHelper(node.left, lvl + 1,
2 * i + 1);
// If the right child of the node
// is not empty, traverse next
// level with index = 2*i + 2
getMaxWidthHelper(node.right, lvl + 1,
2 * i + 2);
}
// Function to find the maximum
// width of the tree
static int getMaxWidth(Node root)
{
// Helper function to fill
// the hashmaps
getMaxWidthHelper(root, 0, 0);
// Traverse to each level and
// find the maximum width
foreach (KeyValuePair<int, int> lvl in hm_max) {
maxx = Math.Max(maxx, hm_max[lvl.Key] - hm_min[lvl.Key] + 1);
}
// Return the result
return maxx;
}
// Driver code
static void Main()
{
/*
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
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.right = new Node(8);
root.right.right.left = new Node(6);
root.right.right.right = new Node(7);
// Function Call
Console.Write(getMaxWidth(root));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// JavaScript program for the above approach
// Tree Node structure
class Node
{
constructor(item)
{
this.data=item;
this.left=this.right=null;
}
}
// Driver Code
let root;
let maxx = 0;
// Stores the position of leftmost
// and rightmost node in each level
let hm_min=new Map();
let hm_max=new Map();
// Function to store the min and the
// max index of each nodes in hashmaps
function getMaxWidthHelper(node,lvl,i)
{
// Base Case
if (node == null) {
return;
}
// Stores rightmost node index
// in the hm_max
if (hm_max.has(lvl)) {
hm_max.set(lvl,
Math.max(
i, hm_max.get(lvl)));
}
else {
hm_max.set(lvl, i);
}
// Stores leftmost node index
// in the hm_min
if (hm_min.has(lvl)) {
hm_min.set(lvl,
Math.min(
i, hm_min.get(lvl)));
}
// Otherwise
else {
hm_min.set(lvl, i);
}
// If the left child of the node
// is not empty, traverse next
// level with index = 2*i + 1
getMaxWidthHelper(node.left, lvl + 1,
2 * i + 1);
// If the right child of the node
// is not empty, traverse next
// level with index = 2*i + 2
getMaxWidthHelper(node.right, lvl + 1,
2 * i + 2);
}
// Function to find the maximum
// width of the tree
function getMaxWidth(root)
{
// Helper function to fill
// the hashmaps
getMaxWidthHelper(root, 0, 0);
// Traverse to each level and
// find the maximum width
for (let [lvl, value] of hm_max.entries()) {
maxx
= Math.max(
maxx,
hm_max.get(lvl)
- hm_min.get(lvl) + 1);
}
// Return the result
return maxx;
}
// Driver Code
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.right = new Node(8);
root.right.right.left = new Node(6);
root.right.right.right = new Node(7);
// Function Call
document.write(getMaxWidth(root));
// This code is contributed by unknown2108
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rv60231023 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA