N-ARY AĞACININ DERINLIĞI

Verilen bir n-ary ağacı Pozitif düğüm değerleri içeren görev, derinlik ağacın.
Not: Bir n-ary ağacı her düğümün sahip olabileceği bir ağaçtır sıfır veya Daha çocuk düğümleri. Düğüm başına en fazla iki çocuğa sahip olan ikili ağaçtan farklı olarak (sol ve sağ) n-ary ağacı şunları sağlar birden fazla şube veya her düğüm için çocuklar.

Örnekler:

Giriş:

Çıkış: 3
Açıklama: Kökten (düğüm 81) yaprağa giden en uzun yol ya 81 -> 26 -> 95 ya da 81 -> 26 -> 86'dır ve maksimum derinlik 3'tür.

Giriş:

Çıkış: 2
Açıklama: Kökten (düğüm 4) herhangi bir yaprağa (düğüm 5 veya 7) giden en uzun yol 2'dir çünkü yalnızca iki düzeyde geçiş gerektirir.

Yaklaşmak:

Fikir hesaplamaktır N-ary ağacının derinliği yinelemeli olarak Başlat maksimum derinlik 0 olarak tekrar tekrar hesaplayın derinlik her çocuk için takip edin ve en yüksek derinlik karşılaştı. Son olarak ekle 1 maksimum derinliğe (geçerli düğüm için) getirin ve sonuç . Bu yaklaşım, bulmamızı sağlar. en uzun yol kökten herhangi bir yaprak düğümüne.

N-Ary ağacı normal bir ağaç gibi geçilebilir. Sadece belirli bir düğümün tüm alt öğelerini dikkate almalı ve bu işlevi her düğümde yinelemeli olarak çağırmalıyız.

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

Çıkış

Zaman Karmaşıklığı: O(n) çünkü her düğüm bir kez ziyaret edilir; burada n, N-ary ağacındaki toplam düğüm sayısıdır.
Yardımcı Alan: O(h) burada h, özyinelemeli çağrı yığını kullanımına bağlı olarak ağacın yüksekliğidir.

Test Oluştur