Una array dada representa un árbol de tal manera que el valor de la array da el Node principal de ese índice en particular. El valor del índice del Node raíz siempre sería -1. Encuentra la altura del árbol.
La altura de un árbol binario es el número de Nodes en el camino desde la raíz hasta el Node hoja más profundo, y el número incluye tanto la raíz como la hoja.
Input: parent[] = {1 5 5 2 2 -1 3}
Output: 4
The given array represents following Binary Tree
5
/ \
1 2
/ / \
0 3 4
/
6
Input: parent[] = {-1, 0, 0, 1, 1, 3, 5};
Output: 5
The given array represents following Binary Tree
0
/ \
1 2
/ \
3 4
/
5
/
6
Recomendado: Resuelva primero en «PRÁCTICA» antes de pasar a la solución.
Fuente: Amazon Experiencia de entrevista | Juego 128 (para SDET)
Recomendamos enfáticamente minimizar su navegador y probarlo usted mismo primero.
Una solución simple es construir primero el árbol y luego encontrar la altura del árbol binario construido. El árbol se puede construir recursivamente buscando primero la raíz actual, luego recurriendo a los índices encontrados y convirtiéndolos en subárboles izquierdo y derecho de la raíz. Esta solución toma O(n 2 ) ya que tenemos que buscar cada Node linealmente.
Una solución eficiente puede resolver el problema anterior en tiempo O(n). La idea es calcular primero la profundidad de cada Node y almacenarla en una array depth[]. Una vez que tenemos las profundidades de todos los Nodes, devolvemos el máximo de todas las profundidades.
- Encuentre la profundidad de todos los Nodes y complete una array auxiliar depth[].
- Devuelve el valor máximo en profundidad[].
Los siguientes son pasos para encontrar la profundidad de un Node en el índice i.
- Si es root, depth[i] es 1.
- Si se evalúa profundidad de padre[i], profundidad[i] es profundidad[padre[i]] + 1.
- Si no se evalúa la profundidad de padre[i], repita para padre y asigne profundidad[i] como profundidad[padre[i]] + 1 (igual que arriba).
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find height using parent array
#include <bits/stdc++.h>
using namespace std;
// This function fills depth of i'th element in parent[].
// The depth is filled in depth[i].
void fillDepth(int parent[], int i, int depth[])
{
// If depth[i] is already filled
if (depth[i])
return;
// If node at index i is root
if (parent[i] == -1) {
depth[i] = 1;
return;
}
// If depth of parent is not evaluated before, then
// evaluate depth of parent first
if (depth[parent[i]] == 0)
fillDepth(parent, parent[i], depth);
// Depth of this node is depth of parent plus 1
depth[i] = depth[parent[i]] + 1;
}
// This function returns height of binary tree represented
// by parent array
int findHeight(int parent[], int n)
{
// Create an array to store depth of all nodes/ and
// initialize depth of every node as 0 (an invalid
// value). Depth of root is 1
int depth[n];
for (int i = 0; i < n; i++)
depth[i] = 0;
// fill depth of all nodes
for (int i = 0; i < n; i++)
fillDepth(parent, i, depth);
// The height of binary tree is maximum of all depths.
// Find the maximum value in depth[] and assign it to
// ht.
int ht = depth[0];
for (int i = 1; i < n; i++)
if (ht < depth[i])
ht = depth[i];
return ht;
}
// Driver program to test above functions
int main()
{
// int parent[] = {1, 5, 5, 2, 2, -1, 3};
int parent[] = { -1, 0, 0, 1, 1, 3, 5 };
int n = sizeof(parent) / sizeof(parent[0]);
cout << "Height is " << findHeight(parent, n);
return 0;
}
Java
// Java program to find height using parent array
class BinaryTree {
// This function fills depth of i'th element in
// parent[]. The depth is filled in depth[i].
void fillDepth(int parent[], int i, int depth[])
{
// If depth[i] is already filled
if (depth[i] != 0) {
return;
}
// If node at index i is root
if (parent[i] == -1) {
depth[i] = 1;
return;
}
// If depth of parent is not evaluated before, then
// evaluate depth of parent first
if (depth[parent[i]] == 0) {
fillDepth(parent, parent[i], depth);
}
// Depth of this node is depth of parent plus 1
depth[i] = depth[parent[i]] + 1;
}
// This function returns height of binary tree
// represented by parent array
int findHeight(int parent[], int n)
{
// Create an array to store depth of all nodes/ and
// initialize depth of every node as 0 (an invalid
// value). Depth of root is 1
int depth[] = new int[n];
for (int i = 0; i < n; i++) {
depth[i] = 0;
}
// fill depth of all nodes
for (int i = 0; i < n; i++) {
fillDepth(parent, i, depth);
}
// The height of binary tree is maximum of all
// depths. Find the maximum value in depth[] and
// assign it to ht.
int ht = depth[0];
for (int i = 1; i < n; i++) {
if (ht < depth[i]) {
ht = depth[i];
}
}
return ht;
}
// Driver program to test above functions
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
// int parent[] = {1, 5, 5, 2, 2, -1, 3};
int parent[] = new int[] { -1, 0, 0, 1, 1, 3, 5 };
int n = parent.length;
System.out.println("Height is "
+ tree.findHeight(parent, n));
}
}
Python3
# Python program to find height using parent array
# This functio fills depth of i'th element in parent[]
# The depth is filled in depth[i]
def fillDepth(parent, i, depth):
# If depth[i] is already filled
if depth[i] != 0:
return
# If node at index i is root
if parent[i] == -1:
depth[i] = 1
return
# If depth of parent is not evaluated before,
# then evaluate depth of parent first
if depth[parent[i]] == 0:
fillDepth(parent, parent[i], depth)
# Depth of this node is depth of parent plus 1
depth[i] = depth[parent[i]] + 1
# This function returns height of binary tree represented
# by parent array
def findHeight(parent):
n = len(parent)
# Create an array to store depth of all nodes and
# initialize depth of every node as 0
# Depth of root is 1
depth = [0 for i in range(n)]
# fill depth of all nodes
for i in range(n):
fillDepth(parent, i, depth)
# The height of binary tree is maximum of all
# depths. Find the maximum in depth[] and assign
# it to ht
ht = depth[0]
for i in range(1, n):
ht = max(ht, depth[i])
return ht
# Driver program to test above function
parent = [-1, 0, 0, 1, 1, 3, 5]
print ("Height is %d" % (findHeight(parent)))
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
using System;
// C# program to find height using parent array
public class BinaryTree {
// This function fills depth of i'th element in
// parent[]. The depth is filled in depth[i].
public virtual void fillDepth(int[] parent, int i,
int[] depth)
{
// If depth[i] is already filled
if (depth[i] != 0) {
return;
}
// If node at index i is root
if (parent[i] == -1) {
depth[i] = 1;
return;
}
// If depth of parent is not evaluated before, then
// evaluate depth of parent first
if (depth[parent[i]] == 0) {
fillDepth(parent, parent[i], depth);
}
// Depth of this node is depth of parent plus 1
depth[i] = depth[parent[i]] + 1;
}
// This function returns height of binary tree
// represented by parent array
public virtual int findHeight(int[] parent, int n)
{
// Create an array to store depth of all nodes/ and
// initialize depth of every node as 0 (an invalid
// value). Depth of root is 1
int[] depth = new int[n];
for (int i = 0; i < n; i++) {
depth[i] = 0;
}
// fill depth of all nodes
for (int i = 0; i < n; i++) {
fillDepth(parent, i, depth);
}
// The height of binary tree is maximum of all
// depths. Find the maximum value in depth[] and
// assign it to ht.
int ht = depth[0];
for (int i = 1; i < n; i++) {
if (ht < depth[i]) {
ht = depth[i];
}
}
return ht;
}
// Driver program to test above functions
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
// int parent[] = {1, 5, 5, 2, 2, -1, 3};
int[] parent = new int[] { -1, 0, 0, 1, 1, 3, 5 };
int n = parent.Length;
Console.WriteLine("Height is "
+ tree.findHeight(parent, n));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// javascript program to find height using parent array
// This function fills depth of i'th element in parent. The depth is
// filled in depth[i].
function fillDepth(parent , i , depth) {
// If depth[i] is already filled
if (depth[i] != 0) {
return;
}
// If node at index i is root
if (parent[i] == -1) {
depth[i] = 1;
return;
}
// If depth of parent is not evaluated before, then evaluate
// depth of parent first
if (depth[parent[i]] == 0) {
fillDepth(parent, parent[i], depth);
}
// Depth of this node is depth of parent plus 1
depth[i] = depth[parent[i]] + 1;
}
// This function returns height of binary tree represented by
// parent array
function findHeight(parent , n) {
// Create an array to store depth of all nodes/ and
// initialize depth of every node as 0 (an invalid
// value). Depth of root is 1
var depth = Array(n).fill(0);
for (i = 0; i < n; i++) {
depth[i] = 0;
}
// fill depth of all nodes
for (i = 0; i < n; i++) {
fillDepth(parent, i, depth);
}
// The height of binary tree is maximum of all depths.
// Find the maximum value in depth and assign it to ht.
var ht = depth[0];
for (i = 1; i < n; i++) {
if (ht < depth[i]) {
ht = depth[i];
}
}
return ht;
}
// Driver program to test above functions
// var parent = [1, 5, 5, 2, 2, -1, 3];
var parent =[-1, 0, 0, 1, 1, 3, 5 ];
var n = parent.length;
document.write("Height is " + findHeight(parent, n));
// This code contributed by gauravrajput1
</script>
Javascript
<script>
// javascript program to find height using parent array
function fillDepth(parent, index, depth, obj) {
let max = depth;
if (obj[index]) {
for (let i = 0; i < obj[index].length; i++) {
max = Math.max(max, fillDepth(parent, obj[index][i], depth + 1, obj))
}
}
return max;
}
// This function returns height of binary tree represented by
// parent array
function findHeight(parent, n) {
let root_index;
for (let i = 0; i < n; i++) {
if (parent[i] === -1) {
root_index = i;
}
}
let obj = {};
for (let i = 0; i < n; i++) {
if (obj[parent[i]]) {
let arr = obj[parent[i]];
arr.push(i)
obj[parent[i]] = arr;
}
else {
obj[parent[i]] = [i];
}
}
return fillDepth(parent, root_index, 1, obj);
}
// Driver program to test above functions
// var parent = [1, 5, 5, 2, 2, -1, 3];
var parent = [-1, 0, 0, 1, 1, 3, 5];
var n = parent.length;
document.write("Height is " + findHeight(parent, n));
// This code contributed by gaurav2146
</script>
Producción
Height is 5
Tenga en cuenta que la complejidad de tiempo de este programa parece más que O (n). Si miramos más de cerca, podemos observar que la profundidad de cada Node se evalúa solo una vez.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA