给定一个父数组P，其中P[i]表示树中第i个节点的父节点（假设根节点id的父节点用-1表示）。找出树的高度。
null
例如：
Input : array[] = [-1 0 1 6 6 0 0 2 7]Output : height = 5Tree formed is: 0 / | 5 1 6 / | 2 4 3 / 7 / 8
1.从每个节点开始，一直到其父节点，直到达到-1。 2.同时，跟踪所有节点之间的最大高度。
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
优化方法 我们使用动态规划。我们将从根到每个节点的高度存储在一个数组中。 所以，如果我们知道根到节点的高度，那么我们可以通过简单地加1得到根到节点子节点的高度。
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
时间复杂度：-O（n） 空间复杂度：-O（n）
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。 本文由 普拉克里蒂·古普塔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
