Djup av ett N-Ary-träd
Givet en n-ärt träd som innehåller positiva nodvärden är uppgiften att hitta djup av trädet.
Notera: En n-ärt träd är ett träd där varje nod kan ha noll eller mer barn noder. Till skillnad från ett binärt träd som har högst två barn per nod (vänster och höger) n-ary-trädet tillåter flera grenar eller barn för varje nod.
Exempel:
Input:
Produktion: 3
Förklaring: Den längsta vägen från roten (nod 81) till ett blad är antingen 81 -> 26 -> 95 eller 81 -> 26 -> 86 vilket ger ett maximalt djup på 3.Input:
Produktion: 2
Förklaring: Den längsta vägen från roten (nod 4) till något löv (nod 5 eller 7) är 2 eftersom den bara kräver två korsningsnivåer.
Närma sig:
Tanken är att beräkna djupet av ett N-ärt träd rekursivt initiera maximalt djup som 0, beräkna sedan rekursivt djup för varje barn och hålla reda på högsta djup stött på. Lägg till sist till 1 till det maximala djupet (för den aktuella noden) och returnera resultat . Detta tillvägagångssätt säkerställer att vi hittar längsta vägen från roten till valfri lövnod.
N-Ary-träd kan korsas precis som ett vanligt träd. Vi måste bara ta hänsyn till alla barn till en given nod och rekursivt anropa den funktionen på varje nod.
C++ // C++ Code to find the depth of an N-ary tree #include using namespace std ; class Node { public : int data ; vector < Node *> children ; Node ( int val ) { data = val ; } }; // Recursive function to calculate maximum depth int maxDepth ( Node * root ) { // If the node is null depth is 0 if ( ! root ) { return 0 ; } int depth = 0 ; // Recur for all children and find the maximum depth for ( auto child : root -> children ) { depth = max ( depth maxDepth ( child )); } // Add 1 to include the current node // in the depth count return depth + 1 ; } int main () { // Representation of given N-ary tree // 1 // / | // 2 3 4 // / // 5 6 Node * root = new Node ( 1 ); root -> children . push_back ( new Node ( 2 )); root -> children . push_back ( new Node ( 3 )); root -> children . push_back ( new Node ( 4 )); root -> children [ 0 ] -> children . push_back ( new Node ( 5 )); root -> children [ 2 ] -> children . push_back ( new Node ( 6 )); cout < < maxDepth ( root ); return 0 ; }
Java // Java Code to find the depth of an N-ary tree import java.util.* ; class Node { int data ; List < Node > children ; Node ( int val ) { data = val ; children = new ArrayList <> (); } } // Recursive function to calculate // maximum depth class GfG { static int maxDepth ( Node root ) { // If the node is null depth is 0 if ( root == null ) { return 0 ; } int depth = 0 ; // Recur for all children and find // the maximum depth for ( Node child : root . children ) { depth = Math . max ( depth maxDepth ( child )); } // Add 1 to include the current node // in the depth count return depth + 1 ; } public static void main ( String [] args ) { // Representation of given N-ary tree // 1 // / | // 2 3 4 // / // 5 6 Node root = new Node ( 1 ); root . children . add ( new Node ( 2 )); root . children . add ( new Node ( 3 )); root . children . add ( new Node ( 4 )); root . children . get ( 0 ). children . add ( new Node ( 5 )); root . children . get ( 2 ). children . add ( new Node ( 6 )); System . out . println ( maxDepth ( root )); } }
Python # Python Code to find the depth # of an N-ary tree class Node : def __init__ ( self val ): self . data = val self . children = [] # Recursive function to calculate # maximum depth def max_depth ( root ): # If the node is None depth is 0 if not root : return 0 depth = 0 # Recur for all children and # find the maximum depth for child in root . children : depth = max ( depth max_depth ( child )) # Add 1 to include the current # node in the depth count return depth + 1 if __name__ == '__main__' : # Representation of given N-ary tree # 1 # / | # 2 3 4 # / # 5 6 root = Node ( 1 ) root . children . append ( Node ( 2 )) root . children . append ( Node ( 3 )) root . children . append ( Node ( 4 )) root . children [ 0 ] . children . append ( Node ( 5 )) root . children [ 2 ] . children . append ( Node ( 6 )) print ( max_depth ( root ))
C# // C# Code to find the depth of an N-ary tree using System ; using System.Collections.Generic ; class Node { public int data ; public List < Node > children ; public Node ( int val ) { data = val ; children = new List < Node > (); } } // Recursive function to calculate // maximum depth class GfG { static int MaxDepth ( Node root ) { // If the node is null depth is 0 if ( root == null ) { return 0 ; } int depth = 0 ; // Recur for all children and find the maximum depth foreach ( Node child in root . children ) { depth = Math . Max ( depth MaxDepth ( child )); } // Add 1 to include the current // node in the depth count return depth + 1 ; } static void Main ( string [] args ) { // Representation of given N-ary tree // 1 // / | // 2 3 4 // / // 5 6 Node root = new Node ( 1 ); root . children . Add ( new Node ( 2 )); root . children . Add ( new Node ( 3 )); root . children . Add ( new Node ( 4 )); root . children [ 0 ]. children . Add ( new Node ( 5 )); root . children [ 2 ]. children . Add ( new Node ( 6 )); Console . WriteLine ( MaxDepth ( root )); } }
JavaScript // JavaScript Code to find the depth // of an N-ary tree class Node { constructor ( val ) { this . data = val ; this . children = []; } } // Recursive function to calculate // maximum depth function maxDepth ( root ) { // If the node is null depth is 0 if ( ! root ) { return 0 ; } let depth = 0 ; // Recur for all children and find // the maximum depth for ( let child of root . children ) { depth = Math . max ( depth maxDepth ( child )); } // Add 1 to include the current node // in the depth count return depth + 1 ; } // Representation of given N-ary tree // 1 // / | // 2 3 4 // / // 5 6 const root = new Node ( 1 ); root . children . push ( new Node ( 2 )); root . children . push ( new Node ( 3 )); root . children . push ( new Node ( 4 )); root . children [ 0 ]. children . push ( new Node ( 5 )); root . children [ 2 ]. children . push ( new Node ( 6 )); console . log ( maxDepth ( root ));
Produktion
3
Tidskomplexitet: O(n) eftersom varje nod besöks en gång där n är det totala antalet noder i det N-ära trädet.
Hjälputrymme: O(h) där h är höjden på trädet på grund av användning av rekursiv anropsstack.
