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>
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>
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