Dada una array principal P, donde P[i] indica el padre del i-ésimo Node en el árbol (suponga que el padre del ID del Node raíz se indica con -1). Encuentra la altura del árbol.
Ejemplos:
Input : array[] = [-1 0 1 6 6 0 0 2 7]
Output : height = 5
Tree formed is:
0
/ | \
5 1 6
/ | \
2 4 3
/
7
/
8
- Comience en cada Node y siga yendo a su padre hasta que lleguemos a -1.
- Además, realice un seguimiento de la altura máxima entre todos los Nodes.
Implementación:
C++
// C++ program to find the height of the generic
// tree(n-ary tree) if parent array is given
#include <bits/stdc++.h>
using namespace std;
// function to find the height of tree
int findHeight(int* parent, int n)
{
int res = 0;
// Traverse each node
for (int i = 0; i < n; i++) {
// traverse to parent until -1
// is reached
int p = i, current = 1;
while (parent[p] != -1) {
current++;
p = parent[p];
}
res = max(res, current);
}
return res;
}
// Driver program
int main()
{
int parent[] = { -1, 0, 1, 6, 6, 0, 0, 2, 7 };
int n = sizeof(parent) / sizeof(parent[0]);
int height = findHeight(parent, n);
cout << "Height of the given tree is: "
<< height << endl;
return 0;
}
Java
// Java program to find the height of
// the generic tree(n-ary tree) if
// parent array is given
import java.io.*;
public class GFG {
// function to find the height of tree
static int findHeight(int[] parent, int n)
{
int res = 0;
// Traverse each node
for (int i = 0; i < n; i++) {
// traverse to parent until -1
// is reached
int p = i, current = 1;
while (parent[p] != -1) {
current++;
p = parent[p];
}
res = Math.max(res, current);
}
return res;
}
// Driver program
static public void main(String[] args)
{
int[] parent = { -1, 0, 1, 6, 6, 0,
0, 2, 7 };
int n = parent.length;
int height = findHeight(parent, n);
System.out.println("Height of the "
+ "given tree is: " + height);
}
}
// This code is contributed by vt_m.
Python3
# Python program to find the height of the generic
# tree(n-ary tree) if parent array is given
# function to find the height of tree
def findHeight(parent, n):
res = 0
# Traverse each node
for i in range(n):
# traverse to parent until -1
# is reached
p = i
current = 1
while (parent[p] != -1):
current+= 1
p = parent[p]
res = max(res, current)
return res
# Driver code
if __name__ == '__main__':
parent = [-1, 0, 1, 6, 6, 0, 0, 2, 7]
n = len(parent)
height = findHeight(parent, n)
print("Height of the given tree is:", height)
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to find the height of
// the generic tree(n-ary tree) if
// parent array is given
using System;
public class GFG {
// function to find the height of tree
static int findHeight(int[] parent, int n)
{
int res = 0;
// Traverse each node
for (int i = 0; i < n; i++) {
// traverse to parent until -1
// is reached
int p = i, current = 1;
while (parent[p] != -1) {
current++;
p = parent[p];
}
res = Math.Max(res, current);
}
return res;
}
// Driver program
static public void Main()
{
int[] parent = { -1, 0, 1, 6, 6, 0,
0, 2, 7 };
int n = parent.Length;
int height = findHeight(parent, n);
Console.WriteLine("Height of the "
+ "given tree is: " + height);
}
}
// This code is contributed by vt_m.
Javascript
<script>
// JavaScript program to find the height of
// the generic tree(n-ary tree) if
// parent array is given
// function to find the height of tree
function findHeight(parent,n)
{
let res = 0;
// Traverse each node
for (let i = 0; i < n; i++) {
// traverse to parent until -1
// is reached
let p = i, current = 1;
while (parent[p] != -1) {
current++;
p = parent[p];
}
res = Math.max(res, current);
}
return res;
}
// Driver program
let parent=[-1, 0, 1, 6, 6, 0,
0, 2, 7];
let n = parent.length;
let height = findHeight(parent, n);
document.write("Height of the "
+ "given tree is: " + height);
// This code is contributed by unknown2108
</script>
Producción:
Height of the given tree is: 5
Enfoque optimizado: Usamos programación dinámica. Almacenamos la altura desde la raíz hasta cada Node en una array. Entonces, si conocemos la altura de la raíz a un Node, entonces podemos obtener la altura de la raíz al Node secundario simplemente sumando 1.
Implementación:
CPP
// C++ program to find the height of the generic
// tree(n-ary tree) if parent array is given
#include <bits/stdc++.h>
using namespace std;
// function to fill the height vector
int rec(int i, int parent[], vector<int> height)
{
// if we have reached root node the
// return 1 as height of root node
if (parent[i] == -1) {
return 1;
}
// if we have calculated height of a
// node then return if
if (height[i] != -1) {
return height[i];
}
// height from root to a node = height
// from root to nodes parent + 1
height[i] = rec(parent[i], parent, height) + 1;
// return nodes height
return height[i];
}
// function to find the height of tree
int findHeight(int* parent, int n)
{
int res = 0;
// vector to store heights of all nodes
vector<int> height(n, -1);
for (int i = 0; i < n; i++) {
res = max(res, rec(i, parent, height));
}
return res;
}
// Driver program
int main()
{
int parent[] = { -1, 0, 1, 6, 6, 0, 0, 2, 7 };
int n = sizeof(parent) / sizeof(parent[0]);
int height = findHeight(parent, n);
cout << "Height of the given tree is: "
<< height << endl;
return 0;
}
Java
// Java program to find the height of the generic
// tree(n-ary tree) if parent array is given
import java.io.*;
import java.util.*;
class GFG {
// function to fill the height vector
static int rec(int i, int parent[], int[] height)
{
// if we have reached root node the
// return 1 as height of root node
if (parent[i] == -1) {
return 1;
}
// if we have calculated height of a
// node then return if
if (height[i] != -1) {
return height[i];
}
// height from root to a node = height
// from root to nodes parent + 1
height[i] = rec(parent[i], parent, height) + 1;
// return nodes height
return height[i];
}
// function to find the height of tree
static int findHeight(int[] parent, int n)
{
int res = 0;
// vector to store heights of all nodes
int height[]=new int[n];
Arrays.fill(height,-1);
for (int i = 0; i < n; i++) {
res = Math.max(res, rec(i, parent, height));
}
return res;
}
// Driver program
public static void main (String[] args) {
int[] parent = { -1, 0, 1, 6, 6, 0, 0, 2, 7 };
int n = parent.length;
int height = findHeight(parent, n);
System.out.println("Height of the given tree is: "+height);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program to find the height of the generic
# tree(n-ary tree) if parent array is given
# function to fill the height vector
def rec(i, parent, height):
# if we have reached root node the
# return 1 as height of root node
if (parent[i] == -1):
return 1
# if we have calculated height of a
# node then return if
if (height[i] != -1):
return height[i]
# height from root to a node = height
# from root to nodes parent + 1
height[i] = rec(parent[i], parent, height) + 1
# return nodes height
return height[i]
# function to find the height of tree
def findHeight(parent, n):
res = 0
# vector to store heights of all nodes
height = [-1]*(n)
for i in range(n):
res = max(res, rec(i, parent, height))
return res
# Driver program
if __name__ == '__main__':
parent = [-1, 0, 1, 6, 6, 0, 0, 2, 7]
n = len(parent)
height = findHeight(parent, n)
print("Height of the given tree is: ",height)
# This code is contributed by mohit kumar 29.
C#
// C# program to find the height of the generic
// tree(n-ary tree) if parent array is given
using System;
public class GFG{
// function to fill the height vector
static int rec(int i, int[] parent, int[] height)
{
// if we have reached root node the
// return 1 as height of root node
if (parent[i] == -1) {
return 1;
}
// if we have calculated height of a
// node then return if
if (height[i] != -1) {
return height[i];
}
// height from root to a node = height
// from root to nodes parent + 1
height[i] = rec(parent[i], parent, height) + 1;
// return nodes height
return height[i];
}
// function to find the height of tree
static int findHeight(int[] parent, int n)
{
int res = 0;
// vector to store heights of all nodes
int[] height = new int[n];
Array.Fill(height, -1);
for (int i = 0; i < n; i++) {
res = Math.Max(res, rec(i, parent, height));
}
return res;
}
// Driver program
static public void Main ()
{
int[] parent = { -1, 0, 1, 6, 6, 0, 0, 2, 7 };
int n = parent.Length;
int height = findHeight(parent, n);
Console.WriteLine("Height of the given tree is: "+height);
}
}
// This code is contributed by ab2127
Javascript
<script>
// Javascript program to find the height of the generic
// tree(n-ary tree) if parent array is given
// function to fill the height vector
function rec(i,parent,height)
{
// if we have reached root node the
// return 1 as height of root node
if (parent[i] == -1) {
return 1;
}
// if we have calculated height of a
// node then return if
if (height[i] != -1) {
return height[i];
}
// height from root to a node = height
// from root to nodes parent + 1
height[i] = rec(parent[i], parent, height) + 1;
// return nodes height
return height[i];
}
// function to find the height of tree
function findHeight(parent,n)
{
let res = 0;
// vector to store heights of all nodes
let height=new Array(n);
for(let i=0;i<n;i++)
{
height[i]=-1;
}
for (let i = 0; i < n; i++) {
res = Math.max(res, rec(i, parent, height));
}
return res;
}
// Driver program
let parent=[-1, 0, 1, 6, 6, 0, 0, 2, 7];
let n=parent.length;
let height = findHeight(parent, n);
document.write("Height of the given tree is: "+height+"<br>");
// This code is contributed by patel2127
</script>
Producción:
Height of the given tree is: 5
Complejidad temporal :- O(n)
Complejidad espacial :- O(n)
Este artículo es una contribución de Prakriti Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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