Requisito previo: ancho máximo de un árbol binario con valor nulo | Serie 1
Dado un árbol binario que consta de N Nodes, la tarea es encontrar el ancho máximo del árbol dado sin usar la recursividad, donde el ancho máximo se define como el máximo de todos los anchos en cada nivel del árbol dado.
Nota: 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:1 // ancho = 1
/ \
2 3 // ancho = 2 – 1 + 1= 2
/ \ \
4 5 8 // ancho = 6 – 3 + 1 = 4
/ \
6 7 // ancho = 8 – 7 + 1 = 2entonces la respuesta es 4
Entrada:
1
/
2
/
3
Salida: 1
Enfoque: En este enfoque, la idea principal es utilizar el orden de nivel transversal y otorgar una identificación a todos los Nodes de acuerdo con su padre, lo que ayudará a encontrar el ancho de un nivel en particular. Los identificadores se distribuyen en este orden particular:
[Node, id: i ]
/ \
[hijo izquierdo, id: (i * 2 +1) ] [hijo derecho, id: (i * 2 + 2) ]
Ahora el ancho de cada nivel se puede calcular usando la fórmula
Ancho del nivel i = (id del primer Node en el nivel i) – (id del último Node en el nivel i) +1
Ilustración: Por ejemplo, utilice el primer ejemplo proporcionado aquí.
{ 1 ,0} // ancho = 1
/ \
{ 2 ,1} { 3 ,2} // ancho = 2 – 1 + 1= 2
/ \ \
{ 4 ,3} { 5 ,4} { 8 ,6 } // ancho = 6 – 3 + 1 = 4
/ \
{ 6 ,7} { 7 ,8} // ancho = 8 – 7 + 1 = 2entonces la respuesta es 4
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;
}
};
// Function to find the width
// of the given tree
int getMaxWidth(Node* root)
{
if (root == NULL) {
return 0;
}
queue<pair<Node*, int> > q;
q.push({ root, 0 });
int maxWidth = 1;
while (!q.empty()) {
int size = q.size();
int first, last;
for (int i = 0; i < size; i++) {
Node* temp = q.front().first;
int id = q.front().second;
q.pop();
// First Node
if (i == 0) {
first = id;
}
// Last Node
if (i == size - 1) {
last = id;
};
if (temp->left)
q.push({ temp->left,
id * 2 + 1 });
if (temp->right)
q.push({ temp->right,
id * 2 + 2 });
}
maxWidth = max(maxWidth,
last - first + 1);
}
return maxWidth;
}
// Driver Code
int main()
{
struct 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
cout << getMaxWidth(root);
return 0;
}
Java
// Java program for the above approach
import java.util.LinkedList;
import java.util.Queue;
class GFG {
// Tree Node structure
public static class Node {
int data;
Node left;
Node right;
// Constructor
public Node(int item) {
this.data = item;
this.left = this.right = null;
}
};
public static class Pair {
Node first;
int second;
public Pair(Node n, int i) {
this.first = n;
this.second = i;
}
}
// Function to find the width
// of the given tree
static int getMaxWidth(Node root) {
if (root == null) {
return 0;
}
Queue<Pair> q = new LinkedList<Pair>();
q.add(new Pair(root, 0));
int maxWidth = 1;
while (!q.isEmpty()) {
int size = q.size();
int first = 0, last = 0;
for (int i = 0; i < size; i++) {
Node temp = q.peek().first;
int id = q.peek().second;
q.remove();
// First Node
if (i == 0) {
first = id;
}
// Last Node
if (i == size - 1) {
last = id;
}
;
if (temp.left != null)
q.add(new Pair(temp.left, id * 2 + 1));
if (temp.right != null)
q.add(new Pair(temp.right, id * 2 + 2));
}
maxWidth = Math.max(maxWidth, last - first + 1);
}
return maxWidth;
}
// Driver Code
public static void main(String args[]) {
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
System.out.println(getMaxWidth(root));
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# Python program for the above approach # Tree Node structure class Node: # Constructor def __init__(self, item): self.data = item self.left = self.right = None # Function to find the width # of the given tree def getMaxWidth(root): if (root == None): return 0 q = [] q.append([root, 0]) maxWidth = 1 while (len(q)): size = len(q) first = None last = None for i in range(size): temp = q[0][0] id = q[0][1] q.pop(0) # First Node if (i == 0): first = id # Last Node if (i == size - 1): last = id if (temp.left): q.append([temp.left, id * 2 + 1]) if (temp.right): q.append([temp.right, id * 2 + 2]) maxWidth = max(maxWidth, last - first + 1) return maxWidth # Driver Code 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 Saurabh jaiswal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Tree Node structure
public class Node {
public int data;
public Node left;
public Node right;
// Constructor
public Node(int item) {
this.data = item;
this.left = this.right = null;
}
};
public class Pair {
public Node first;
public int second;
public Pair(Node n, int i) {
this.first = n;
this.second = i;
}
}
// Function to find the width
// of the given tree
static int getMaxWidth(Node root) {
if (root == null) {
return 0;
}
Queue<Pair> q = new Queue<Pair>();
q.Enqueue(new Pair(root, 0));
int maxWidth = 1;
while (q.Count!=0) {
int size = q.Count;
int first = 0, last = 0;
for (int i = 0; i < size; i++) {
Node temp = q.Peek().first;
int id = q.Peek().second;
q.Dequeue();
// First Node
if (i == 0) {
first = id;
}
// Last Node
if (i == size - 1) {
last = id;
}
;
if (temp.left != null)
q.Enqueue(new Pair(temp.left, id * 2 + 1));
if (temp.right != null)
q.Enqueue(new Pair(temp.right, id * 2 + 2));
}
maxWidth = Math.Max(maxWidth, last - first + 1);
}
return maxWidth;
}
// Driver Code
public static void Main(String []args) {
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.WriteLine(getMaxWidth(root));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Tree Node structure
class Node {
// Constructor
constructor(item) {
this.data = item;
this.left = this.right = null;
}
};
// Function to find the width
// of the given tree
function getMaxWidth(root) {
if (root == null) {
return 0;
}
let q = [];
q.push([root, 0]);
let maxWidth = 1;
while (q.length) {
let size = q.length;
let first, last;
for (let i = 0; i < size; i++) {
let temp = q[0][0];
let id = q[0][1];
q.shift();
// First Node
if (i == 0) {
first = id;
}
// Last Node
if (i == size - 1) {
last = id;
};
if (temp.left)
q.push([temp.left, id * 2 + 1]);
if (temp.right)
q.push([temp.right, id * 2 + 2]);
}
maxWidth = Math.max(maxWidth, last - first + 1);
}
return maxWidth;
}
// Driver Code
let 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 gfgking.
</script>
4
Complejidad temporal : O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por prasanna1995 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA