N-Ary koka dziļums
Ņemot vērā an n-ārais koks satur pozitīvas mezgla vērtības, uzdevums ir atrast dziļums no koka.
Piezīme: An n-ārais koks ir koks, kurā var būt katrs mezgls nulle vai vairāk bērnu mezgli. Atšķirībā no binārā koka, kuram ir ne vairāk kā divi bērni vienā mezglā (pa kreisi un pa labi) n-ārais koks pieļauj vairākas filiāles vai bērni katram mezglam.
Piemēri:
Ievade:
Izvade: 3
Paskaidrojums: Garākais ceļš no saknes (81. mezgls) līdz lapai ir 81 -> 26 -> 95 vai 81 -> 26 -> 86, kas nodrošina maksimālo dziļumu 3.Ievade:
Izvade: 2
Paskaidrojums: Garākais ceļš no saknes (mezgls 4) uz jebkuru lapu (mezgls 5 vai 7) ir 2, jo tam ir nepieciešami tikai divi šķērsošanas līmeņi.
Pieeja:
Ideja ir aprēķināt N-āru koka dziļums rekursīvi inicializēt maksimālais dziļums kā 0, tad rekursīvi aprēķiniet dziļums katram bērnam un sekojiet līdzi lielākais dziļums sastaptas. Visbeidzot pievienojiet 1 līdz maksimālajam dziļumam (pašreizējam mezglam) un atgrieziet rezultāts . Šī pieeja nodrošina, ka mēs atrodam garākais ceļš no saknes līdz jebkuram lapas mezglam.
N-Ary koku var šķērsot tāpat kā parastu koku. Mums vienkārši jāņem vērā visi noteiktā mezgla bērni un rekursīvi jāizsauc šī funkcija katrā mezglā.
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 ));
Izvade
3
Laika sarežģītība: O(n), jo katrs mezgls tiek apmeklēts vienreiz, kur n ir kopējais mezglu skaits N-ārā kokā.
Palīgtelpa: O(h) kur h ir koka augstums rekursīvā izsaukuma steka lietošanas dēļ.
