PROFUNDITAT D'UN ARBRE N-ARI

Donat un arbre n-ari que conté valors de nodes positius, la tasca és trobar el profunditat de l'arbre.
Nota: An arbre n-ari és un arbre on pot tenir cada node zero o més nodes fills. A diferència d'un arbre binari que té com a màxim dos fills per node (esquerra i dreta) l'arbre n-ari permet múltiples branques o fills per a cada node.

Exemples:

Entrada:

Sortida: 3
Explicació: El camí més llarg des de l'arrel (node 81) fins a una fulla és 81 -> 26 -> 95 o 81 -> 26 -> 86 amb una profunditat màxima de 3.

Entrada:

Sortida: 2
Explicació: El camí més llarg des de l'arrel (node 4) fins a qualsevol fulla (nodes 5 o 7) és 2, ja que només requereix dos nivells de recorregut.

Enfocament:

La idea és calcular el profunditat d'un arbre N-ari recursivament inicialitzar el profunditat màxima com a 0, calculeu recursivament el profunditat per a cada nen i fer-ne un seguiment profunditat més alta trobada. Finalment afegir 1 a la profunditat màxima (per al node actual) i retornar el resultat . Aquest enfocament garanteix que trobem el camí més llarg des de l'arrel fins a qualsevol node full.

L'arbre N-Ary es pot travessar igual que un arbre normal. Només hem de considerar tots els fills d'un node donat i cridar recursivament aquesta funció a cada node.

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# 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  ));

Sortida

Complexitat temporal: O(n) ja que cada node es visita una vegada, on n és el nombre total de nodes de l'arbre N-ari.
Espai auxiliar: O(h) on h és l'alçada de l'arbre a causa de l'ús recursiu de la pila de trucades.

Crea un qüestionari