Adâncimea unui copac N-ari
Având în vedere o arbore n-ary care conțin valori pozitive ale nodurilor, sarcina este de a găsi adâncime a copacului.
Nota: Un arbore n-ary este un arbore în care fiecare nod poate avea zero sau Mai mult nodurile copiilor. Spre deosebire de un arbore binar care are cel mult doi copii pe nod (stânga și dreapta) arborele n-ary permite mai multe ramuri sau copii pentru fiecare nod.
Exemple:
Intrare:
Ieșire: 3
Explicaţie: Cea mai lungă cale de la rădăcină (nodul 81) la o frunză este fie 81 -> 26 -> 95, fie 81 -> 26 -> 86, oferind o adâncime maximă de 3.Intrare:
Ieșire: 2
Explicaţie: Cea mai lungă cale de la rădăcină (nodul 4) la orice frunză (nodurile 5 sau 7) este 2, deoarece necesită doar două niveluri de traversare.
Abordare:
Ideea este de a calcula adâncimea unui arbore N-ary recursiv inițializați adâncime maximă ca 0 apoi calculați recursiv adâncime pentru fiecare copil și ține evidența cea mai mare adâncime întâlnit. În cele din urmă adăugați 1 la adâncimea maximă (pentru nodul curent) și returnați rezultat . Această abordare ne asigură că găsim calea cea mai lungă de la rădăcină la orice nod frunză.
Arborele N-Ary poate fi traversat la fel ca un copac normal. Trebuie doar să luăm în considerare toți copiii unui nod dat și să apelăm recursiv acea funcție pe fiecare 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 ));
Ieșire
3
Complexitatea timpului: O(n) deoarece fiecare nod este vizitat o dată, unde n este numărul total de noduri din arborele N-ary.
Spațiu auxiliar: O(h) unde h este înălțimea arborelui din cauza utilizării recursive a stivei de apeluri.
