Largura máxima de uma árvore binária com valor nulo
Dada uma árvore binária que consiste em N nós, a tarefa é encontrar a largura máxima da árvore dada, onde a largura máxima é definida como o máximo de todas as larguras em cada nível da árvore dada.
A largura de uma árvore para qualquer nível é definida como o número de nós entre os dois nós extremos desse nível, incluindo o nó NULL entre eles.
Exemplos:
Entrada:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
Saída: 4
Explicação:
A largura do nível 1 é 1
A largura do nível 2 é 2
A largura do nível 3 é 4 (porque tem um nó nulo entre 5 e 8)
A largura do nível 4 é 2Portanto, a largura máxima da árvore é o máximo de todas as larguras, ou seja, máx. {1, 2, 4, 2} = 4.
Entrada:
1
/
2
/
3
de saída: 1
Abordagem: O problema fornecido pode ser resolvido representando a Árvore Binária como a representação de array do Heap . Suponha que o índice de um nó seja i, então os índices de seus filhos são (2 * i + 1) e (2 * i + 2) . Agora, para cada nível, encontre a posição do nó mais à esquerda e do nó mais à direita em cada nível, então a diferença entre eles dará a largura desse nível. Siga as etapas abaixo para resolver este problema:
- Inicialize dois HashMap , digamos HMMax e HMMin que armazena a posição do nó mais à esquerda e do nó mais à direita em cada nível
- Crie uma função recursiva getMaxWidthHelper (root, lvl, i) que obtém a raiz da árvore, nível inicial da árvore inicialmente 0 e posição do nó raiz da árvore inicialmente 0 e execute as seguintes etapas:
- Se a raiz da árvore for NULL , retorne.
- Armazene o índice do nó mais à esquerda no nível lvl no HMMin .
- Armazene o índice do nó mais à direita no nível lvl no HMMax .
- Chamada de forma recursiva para a sub-árvore esquerda, atualizando o valor do lvl para lvl + 1 e i a (2 * i + 1) .
- Chamada de forma recursiva para a sub-árvore direita, atualizando o valor do lvl para lvl + 1 e i a (2 * i + 2) .
- Chame a função getMaxWidthHelper (root, 0, 0) para preencher o HashMap.
- Depois de completar os passos acima, imprimir o valor máximo de (HMMax (L) - HMMin (L) + 1) entre todos os possíveis valores de nível L .
Abaixo está a implementação da abordagem acima:
// 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.second] -
hm_min[lvl.second] + 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 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 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# 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.<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>Saída:
4
Complexidade de tempo: O (N)
Espaço auxiliar: O (N)
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva
