ЗНАЙТИ ВИСОТУ СПЕЦІАЛЬНОГО БІНАРНОГО ДЕРЕВА, ЛИСТОВІ ВУЗЛИ ЯКОГО З’ЄДНАНІ

Враховуючи а спеціальне бінарне дерево чий листкові вузли з’єднані у форму a кільцевий двозв'язний список завдання знайти висота дерева.

приклади:

введення:

Вихід: 2
Пояснення: Висота бінарного дерева після розпізнавання листових вузлів дорівнює 2. У наведеному вище двійковому дереві 6, 5 і 4 є листовими вузлами, і вони утворюють кільцевий подвійний зв’язаний список. Тут лівий покажчик кінцевого вузла діятиме як попередній покажчик кільцевого двозв’язаного списку, а його правий вказівник діятиме як наступний вказівник кільцевого двозв’язаного списку.

введення:

Вихід: 1
Пояснення: Висота бінарного дерева після розпізнавання листових вузлів дорівнює 1. У наведеному вище бінарному дереві 2 і 3 є листовими вузлами, і вони утворюють кільцевий подвійний зв’язаний список.

Підхід :

Ідея полягає в тому, щоб слідувати аналогічний підхід як ми робимо для знаходження висоти нормального бінарного дерева . ми рекурсивно розрахувати висота з ліворуч і праворуч піддерева вузла та присвоїти висота до вузла як макс висот двох дітей плюс 1. Але ліва і права дочірні частини a листовий вузол є нульовими для звичайних бінарних дерев. Але тут листовий вузол є кільцевим подвійно зв’язаним вузлом списку. Отже, щоб вузол був листовим вузлом, ми перевіряємо чи вузол лівий правий вказує на вузол і його справа ліворуч також вказує на вузол себе.

C++

    // C++ program to calculate height of a special tree   // whose leaf nodes forms a circular doubly linked list   #include          using     namespace     std  ;   class     Node     {   public  :      int     data  ;      Node     *  left       *  right  ;      Node  (  int     x  )     {      data     =     x  ;      left     =     nullptr  ;      right     =     nullptr  ;      }   };   // function to check if given    // node is a leaf node or node   bool     isLeaf  (  Node  *     node  )     {          // For a node to be a leaf node it should      // satisfy the following two conditions:      // 1. Node's left's right pointer should be       // current node.      // 2. Node's right's left pointer should be       // current node.          // If one condition is met it is guaranteed      // that the other consition is also true.      return     node  ->  left     &&     node  ->  left  ->  right     ==     node      &&     node  ->  right     &&     node  ->  right  ->  left     ==     node  ;   }   // Compute the height of a tree    int     findTreeHeight  (  Node  *     node  )     {          // if node is NULL return -1.      if     (  node     ==     nullptr  )      return     -1  ;      // if node is a leaf node return 0      if     (  isLeaf  (  node  ))      return     0  ;      // compute the depth of each subtree      // and take maximum      return     1     +     max  (  findTreeHeight  (  node  ->  left  )         findTreeHeight  (  node  ->  right  ));   }   int     main  ()     {          Node  *     root     =     new     Node  (  1  );      root  ->  left     =     new     Node  (  2  );      root  ->  right     =     new     Node  (  3  );      root  ->  left  ->  left     =     new     Node  (  4  );      root  ->  left  ->  right     =     new     Node  (  5  );      root  ->  left  ->  left  ->  left     =     new     Node  (  6  );      // Given tree contains 3 leaf nodes      Node  *     l1     =     root  ->  left  ->  left  ->  left  ;      Node  *     l2     =     root  ->  left  ->  right  ;      Node  *     l3     =     root  ->  right  ;      // create circular doubly linked list out of      // leaf nodes of the tree      // set next pointer of linked list      l1  ->  right     =     l2       l2  ->  right     =     l3       l3  ->  right     =     l1  ;      // set prev pointer of linked list      l3  ->  left     =     l2       l2  ->  left     =     l1       l1  ->  left     =     l3  ;      cout      < <     findTreeHeight  (  root  );      return     0  ;   }

    // C program to calculate height of a special tree   // whose leaf nodes forms a circular doubly linked list   #include         #include         struct     Node     {      int     data  ;      struct     Node     *  left       *  right  ;   };   // function to check if given    // node is a leaf node or node   int     isLeaf  (  struct     Node  *     node  )     {          // For a node to be a leaf node it should      // satisfy the following two conditions:      // 1. Node's left's right pointer should be       // current node.      // 2. Node's right's left pointer should be       // current node.          // If one condition is met it is guaranteed      // that the other condition is also true.      return     node  ->  left     &&     node  ->  left  ->  right     ==     node      &&     node  ->  right     &&     node  ->  right  ->  left     ==     node  ;   }   // Compute the height of a tree    int     findTreeHeight  (  struct     Node  *     node  )     {          // if node is NULL return -1.      if     (  node     ==     NULL  )      return     -1  ;      // if node is a leaf node return 0      if     (  isLeaf  (  node  ))      return     0  ;      // compute the depth of each subtree and take maximum      int     leftDepth     =     findTreeHeight  (  node  ->  left  );      int     rightDepth     =     findTreeHeight  (  node  ->  right  );      return     1     +     (  leftDepth     >     rightDepth     ?     leftDepth     :     rightDepth  );   }   struct     Node  *     createNode  (  int     data  )     {      struct     Node  *     newNode     =         (  struct     Node  *  )  malloc  (  sizeof  (  struct     Node  ));      newNode  ->  data     =     data  ;      newNode  ->  left     =     NULL  ;      newNode  ->  right     =     NULL  ;      return     newNode  ;   }   int     main  ()     {          struct     Node  *     root     =     createNode  (  1  );      root  ->  left     =     createNode  (  2  );      root  ->  right     =     createNode  (  3  );      root  ->  left  ->  left     =     createNode  (  4  );      root  ->  left  ->  right     =     createNode  (  5  );      root  ->  left  ->  left  ->  left     =     createNode  (  6  );      // Given tree contains 3 leaf nodes      struct     Node  *     l1     =     root  ->  left  ->  left  ->  left  ;      struct     Node  *     l2     =     root  ->  left  ->  right  ;      struct     Node  *     l3     =     root  ->  right  ;      // create circular doubly linked list out of      // leaf nodes of the tree      // set next pointer of linked list      l1  ->  right     =     l2       l2  ->  right     =     l3       l3  ->  right     =     l1  ;      // set prev pointer of linked list      l3  ->  left     =     l2       l2  ->  left     =     l1       l1  ->  left     =     l3  ;      printf  (  '%d'       findTreeHeight  (  root  ));      return     0  ;   }

Java

    // Java program to calculate height of a special tree   // whose leaf nodes forms a circular doubly linked list   class   Node     {      int     data  ;      Node     left       right  ;      Node  (  int     x  )     {      data     =     x  ;      left     =     null  ;      right     =     null  ;      }   }   class   GfG     {      // function to check if given       // node is a leaf node or node      static     boolean     isLeaf  (  Node     node  )     {          // For a node to be a leaf node it should      // satisfy the following two conditions:      // 1. Node's left's right pointer should be       // current node.      // 2. Node's right's left pointer should be       // current node.          // If one condition is met it is guaranteed      // that the other condition is also true.      return     node  .  left     !=     null     &&     node  .  left  .  right     ==     node      &&     node  .  right     !=     null     &&     node  .  right  .  left     ==     node  ;      }      // Compute the height of a tree       static     int     findTreeHeight  (  Node     node  )     {          // if node is NULL return -1.      if     (  node     ==     null  )      return     -  1  ;      // if node is a leaf node return 0      if     (  isLeaf  (  node  ))      return     0  ;      // compute the depth of each subtree and take maximum      return     1     +     Math  .  max  (  findTreeHeight  (  node  .  left  )         findTreeHeight  (  node  .  right  ));      }      public     static     void     main  (  String  []     args  )     {      Node     root     =     new     Node  (  1  );      root  .  left     =     new     Node  (  2  );      root  .  right     =     new     Node  (  3  );      root  .  left  .  left     =     new     Node  (  4  );      root  .  left  .  right     =     new     Node  (  5  );      root  .  left  .  left  .  left     =     new     Node  (  6  );      // Given tree contains 3 leaf nodes      Node     l1     =     root  .  left  .  left  .  left  ;      Node     l2     =     root  .  left  .  right  ;      Node     l3     =     root  .  right  ;      // create circular doubly linked list out of      // leaf nodes of the tree      // set next pointer of linked list      l1  .  right     =     l2  ;      l2  .  right     =     l3  ;      l3  .  right     =     l1  ;      // set prev pointer of linked list      l3  .  left     =     l2  ;      l2  .  left     =     l1  ;      l1  .  left     =     l3  ;      System  .  out  .  println  (  findTreeHeight  (  root  ));      }   }

Python

    # Python program to calculate height of a special tree   # whose leaf nodes forms a circular doubly linked list   class   Node  :   def   __init__  (  self     data  ):   self  .  data   =   data   self  .  left   =   None   self  .  right   =   None   # function to check if given    # node is a leaf node or node   def   isLeaf  (  node  ):   # For a node to be a leaf node it should   # satisfy the following two conditions:   # 1. Node's left's right pointer should be    # current node.   # 2. Node's right's left pointer should be    # current node.   # If one condition is met it is guaranteed   # that the other condition is also true.   return   (  node  .  left   and   node  .  left  .  right   ==   node   and   node  .  right   and   node  .  right  .  left   ==   node  )   # Compute the height of a tree    def   findTreeHeight  (  node  ):   # if node is NULL return -1.   if   node   is   None  :   return   -  1   # if node is a leaf node return 0   if   isLeaf  (  node  ):   return   0   # compute the depth of each subtree and take maximum   return   1   +   max  (  findTreeHeight  (  node  .  left  )   findTreeHeight  (  node  .  right  ))   if   __name__   ==   '__main__'  :   root   =   Node  (  1  )   root  .  left   =   Node  (  2  )   root  .  right   =   Node  (  3  )   root  .  left  .  left   =   Node  (  4  )   root  .  left  .  right   =   Node  (  5  )   root  .  left  .  left  .  left   =   Node  (  6  )   # Given tree contains 3 leaf nodes   l1   =   root  .  left  .  left  .  left   l2   =   root  .  left  .  right   l3   =   root  .  right   # create circular doubly linked list out of   # leaf nodes of the tree   # set next pointer of linked list   l1  .  right   =   l2   l2  .  right   =   l3   l3  .  right   =   l1   # set prev pointer of linked list   l3  .  left   =   l2   l2  .  left   =   l1   l1  .  left   =   l3   print  (  findTreeHeight  (  root  ))

    // C# program to calculate height of a special tree   // whose leaf nodes forms a circular doubly linked list   using     System  ;   class     Node     {      public     int     data  ;      public     Node     left       right  ;      public     Node  (  int     x  )     {      data     =     x  ;      left     =     null  ;      right     =     null  ;      }   }   class     GfG     {      // function to check if given       // node is a leaf node or node      static     bool     isLeaf  (  Node     node  )     {          // For a node to be a leaf node it should      // satisfy the following two conditions:      // 1. Node's left's right pointer should be       // current node.      // 2. Node's right's left pointer should be       // current node.          // If one condition is met it is guaranteed      // that the other condition is also true.      return     node  .  left     !=     null     &&     node  .  left  .  right     ==     node      &&     node  .  right     !=     null     &&     node  .  right  .  left     ==     node  ;      }      // Compute the height of a tree       static     int     findTreeHeight  (  Node     node  )     {          // if node is NULL return -1.      if     (  node     ==     null  )      return     -  1  ;      // if node is a leaf node return 0      if     (  isLeaf  (  node  ))      return     0  ;      // compute the depth of each subtree and take maximum      return     1     +     Math  .  Max  (  findTreeHeight  (  node  .  left  )     findTreeHeight  (  node  .  right  ));      }      static     void     Main  (  string  []     args  )     {      Node     root     =     new     Node  (  1  );      root  .  left     =     new     Node  (  2  );      root  .  right     =     new     Node  (  3  );      root  .  left  .  left     =     new     Node  (  4  );      root  .  left  .  right     =     new     Node  (  5  );      root  .  left  .  left  .  left     =     new     Node  (  6  );      // Given tree contains 3 leaf nodes      Node     l1     =     root  .  left  .  left  .  left  ;      Node     l2     =     root  .  left  .  right  ;      Node     l3     =     root  .  right  ;      // create circular doubly linked list out of      // leaf nodes of the tree      // set next pointer of linked list      l1  .  right     =     l2  ;      l2  .  right     =     l3  ;      l3  .  right     =     l1  ;      // set prev pointer of linked list      l3  .  left     =     l2  ;      l2  .  left     =     l1  ;      l1  .  left     =     l3  ;      Console  .  WriteLine  (  findTreeHeight  (  root  ));      }   }

JavaScript

    // JavaScript program to calculate height of a special tree   // whose leaf nodes forms a circular doubly linked list   class     Node     {      constructor  (  data  )     {      this  .  data     =     data  ;      this  .  left     =     null  ;      this  .  right     =     null  ;      }   }   // function to check if given    // node is a leaf node or node   function     isLeaf  (  node  )     {          // For a node to be a leaf node it should      // satisfy the following two conditions:      // 1. Node's left's right pointer should be       // current node.      // 2. Node's right's left pointer should be       // current node.          // If one condition is met it is guaranteed      // that the other condition is also true.      return     node  .  left     &&     node  .  left  .  right     ===     node      &&     node  .  right     &&     node  .  right  .  left     ===     node  ;   }   // Compute the height of a tree    function     findTreeHeight  (  node  )     {          // if node is NULL return -1.      if     (  node     ===     null  )      return     -  1  ;      // if node is a leaf node return 0      if     (  isLeaf  (  node  ))      return     0  ;      // compute the depth of each subtree and take maximum      return     1     +     Math  .  max  (  findTreeHeight  (  node  .  left  )     findTreeHeight  (  node  .  right  ));   }   const     root     =     new     Node  (  1  );   root  .  left     =     new     Node  (  2  );   root  .  right     =     new     Node  (  3  );   root  .  left  .  left     =     new     Node  (  4  );   root  .  left  .  right     =     new     Node  (  5  );   root  .  left  .  left  .  left     =     new     Node  (  6  );   // Given tree contains 3 leaf nodes   const     l1     =     root  .  left  .  left  .  left  ;   const     l2     =     root  .  left  .  right  ;   const     l3     =     root  .  right  ;   // create circular doubly linked list out of   // leaf nodes of the tree   // set next pointer of linked list   l1  .  right     =     l2  ;   l2  .  right     =     l3  ;   l3  .  right     =     l1  ;   // set prev pointer of linked list   l3  .  left     =     l2  ;   l2  .  left     =     l1  ;   l1  .  left     =     l3  ;   console  .  log  (  findTreeHeight  (  root  ));