给定父数组时n元树的高度

给定一个父数组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
喜欢就支持一下吧
点赞15 分享