Рубрики

Проверьте, все ли листья на одном уровне

Учитывая Двоичное Дерево, проверьте, все ли листья на одном уровне или нет.

          12
        /    \
      5       7       
    /          \ 
   3            1
  Leaves are at same level

          12
        /    \
      5       7       
    /          
   3          
   Leaves are Not at same level


          12
        /    
      5             
    /   \        
   3     9
  /      /
 1      2
 Leaves are at same level

Метод 1 (рекурсивный)

Идея состоит в том, чтобы сначала найти уровень самого левого листа и сохранить его в переменной leafLevel. Затем сравните уровень всех остальных листьев с leafLevel, если он такой же, верните true, иначе верните false. Мы пересекаем данное двоичное дерево в порядке предварительного заказа. Уровень аргумента передается всем вызовам. Значение leafLevel инициализируется как 0, чтобы указать, что первый лист еще не виден. Значение обновляется, когда мы находим первый лист. Уровень последующих листьев (в предзаказе) сравнивается с leafLevel.

C ++

// C ++ программа для проверки, все ли уходит
// на одном уровне
#include <bits/stdc++.h>

using namespace std;

  
// Узел двоичного дерева

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Сервисная функция для выделения
// новый узел дерева

struct Node* newNode(int data)

{

    struct Node* node = (struct Node*) malloc(sizeof(struct Node));

    node->data = data;

    node->left = node->right = NULL;

    return node;

}

  
/ * Рекурсивная функция, которая проверяет,
все листья на одном уровне * /

bool checkUtil(struct Node *root, 

            int level, int *leafLevel)

{

    // Базовый вариант

    if (root == NULL) return true;

  

    // Если встречается листовой узел

    if (root->left == NULL && 

        root->right == NULL)

    {

        // Когда найден листовой узел

        // первый раз

        if (*leafLevel == 0)

        {

            *leafLevel = level; // Установить уровень первого найденного листа

            return true;

        }

  

        // Если это не первый листовой узел, сравниваем

        // его уровень с уровнем первого листа

        return (level == *leafLevel);

    }

  

    // Если этот узел не лист, рекурсивно

    // проверяем левое и правое поддеревья

    return checkUtil(root->left, level + 1, leafLevel) &&

            checkUtil(root->right, level + 1, leafLevel);

}

  
/ * Основная функция для проверки
если все листья на одном уровне.
В основном использует checkUtil () * /

bool check(struct Node *root)

{

    int level = 0, leafLevel = 0;

    return checkUtil(root, level, &leafLevel);

}

  
// Код драйвера

int main()

{

    // Давайте создадим дерево, показанное в третьем примере

    struct Node *root = newNode(12);

    root->left = newNode(5);

    root->left->left = newNode(3);

    root->left->right = newNode(9);

    root->left->left->left = newNode(1);

    root->left->right->left = newNode(1);

    if (check(root))

        cout << "Leaves are at same level\n";

    else

        cout << "Leaves are not at same level\n";

    getchar();

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

// C программа для проверки, все ли листья на одном уровне
#include <stdio.h>
#include <stdlib.h>

  
// Узел двоичного дерева

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Вспомогательная функция для выделения нового узла дерева

struct Node* newNode(int data)

{

    struct Node* node = (struct Node*) malloc(sizeof(struct Node));

    node->data = data;

    node->left = node->right = NULL;

    return node;

}

  
/ * Рекурсивная функция, которая проверяет, все ли листья находятся на одном уровне * /

bool checkUtil(struct Node *root, int level, int *leafLevel)

{

    // Базовый вариант

    if (root == NULL)  return true;

  

    // Если встречается листовой узел

    if (root->left == NULL && root->right == NULL)

    {

        // Когда листовой узел найден впервые

        if (*leafLevel == 0)

        {

            *leafLevel = level; // Установить уровень первого найденного листа

            return true;

        }

  

        // Если это не первый листовой узел, сравниваем его уровень с

        // уровень первого листа

        return (level == *leafLevel);

    }

  

    // Если этот узел не листовой, рекурсивно проверяем левое и правое поддеревья

    return checkUtil(root->left, level+1, leafLevel) &&

           checkUtil(root->right, level+1, leafLevel);

}

  
/ * Основная функция, чтобы проверить, все ли листья находятся на одном уровне.

   В основном использует checkUtil () * /

bool check(struct Node *root)

{

   int level = 0, leafLevel = 0;

   return checkUtil(root, level, &leafLevel);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    // Давайте создадим дерево, показанное в третьем примере

    struct Node *root = newNode(12);

    root->left = newNode(5);

    root->left->left = newNode(3);

    root->left->right = newNode(9);

    root->left->left->left = newNode(1);

    root->left->right->left = newNode(1);

    if (check(root))

        printf("Leaves are at same level\n");

    else

        printf("Leaves are not at same level\n");

    getchar();

    return 0;

}

Джава

// Java-программа для проверки, все ли листья находятся на одном уровне

   
// Узел двоичного дерева

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class Leaf 

{

    int leaflevel=0;

}

   

class BinaryTree 

{

    Node root;

    Leaf mylevel = new Leaf();

      

    / * Рекурсивная функция, которая проверяет, все ли листья одинаковы

       уровень * /

    boolean checkUtil(Node node, int level, Leaf leafLevel) 

    {

        // Базовый вариант

        if (node == null)

            return true;

              

        // Если встречается листовой узел

        if (node.left == null && node.right == null

        {

            // Когда листовой узел найден впервые

            if (leafLevel.leaflevel == 0

            {

                // Установить уровень первого найденного листа

                leafLevel.leaflevel = level; 

                return true;

            }

   

            // Если это не первый листовой узел, сравниваем его уровень с

            // уровень первого листа

            return (level == leafLevel.leaflevel);

        }

   

        // Если этот узел не листовой, рекурсивно проверяем левую и правую

        // поддеревья

        return checkUtil(node.left, level + 1, leafLevel)

                && checkUtil(node.right, level + 1, leafLevel);

    }

   

    / * Основная функция, чтобы проверить, все ли листья находятся на одном уровне.

       В основном использует checkUtil () * /

    boolean check(Node node) 

    {

        int level = 0;

        return checkUtil(node, level, mylevel);

    }

   

    public static void main(String args[]) 

    {

        // Давайте создадим дерево, как показано в примере

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(12);

        tree.root.left = new Node(5);

        tree.root.left.left = new Node(3);

        tree.root.left.right = new Node(9);

        tree.root.left.left.left = new Node(1);

        tree.root.left.right.left = new Node(1);

        if (tree.check(tree.root))

            System.out.println("Leaves are at same level");

        else

            System.out.println("Leaves are not at same level");

    }

}

   
// Этот код предоставлен Mayank Jaiswal

питон

# Программа Python, чтобы проверить, все ли листья находятся на одном уровне

  
# Узел двоичного дерева

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Рекурсивная функция, которая проверяет, все ли листья в
# тот же уровень

def checkUtil(root, level):

      

    # Базовый вариант

    if root is None:

        return True

      

    # Если встречается узел дерева

    if root.left is None and root.right is None:

          

        # Когда листовой узел найден впервые

        if check.leafLevel == 0 :

            check.leafLevel = level # Установить первый найденный лист

            return True

  

        # Если это не первый листовой узел, сравните его уровень

        # с уровня первого листа

        return level == check.leafLevel 

  

    # Если это не первый листовой узел, сравните его уровень

    # с уровня первого листа

    return (checkUtil(root.left, level+1)and

            checkUtil(root.right, level+1))

  

def check(root):

    level = 0

    check.leafLevel = 0 

    return (checkUtil(root, level))

  
# Программа драйвера для проверки вышеуказанной функции

root = Node(12)

root.left = Node(5)

root.left.left = Node(3)

root.left.right = Node(9)

root.left.left.left = Node(1)

root.left.right.left = Node(2)

  

if(check(root)):

    print "Leaves are at same level"

else:

    print "Leaves are not at same level"

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для проверки, все ли уходит
// на одном уровне

using System;

  
// Узел двоичного дерева

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class Leaf

{

    public int leaflevel = 0;

}

  

class GFG

{

public Node root;

public Leaf mylevel = new Leaf();

  
/ * Рекурсивная функция, которая проверяет
все ли листья на одном уровне * /

public virtual bool checkUtil(Node node, int level,

                              Leaf leafLevel)

{

    // Базовый вариант

    if (node == null)

    {

        return true;

    }

  

    // Если встречается листовой узел

    if (node.left == null && node.right == null)

    {

        // Когда листовой узел найден впервые

        if (leafLevel.leaflevel == 0)

        {

            // Установить уровень первого найденного листа

            leafLevel.leaflevel = level;

            return true;

        }

  

        // Если это не первый листовой узел,

        // сравниваем его уровень с уровнем первого листа

        return (level == leafLevel.leaflevel);

    }

  

    // Если этот узел не лист, рекурсивно

    // проверяем левое и правое поддеревья

    return checkUtil(node.left, level + 1, leafLevel) && 

           checkUtil(node.right, level + 1, leafLevel);

}

  
/ * Основная функция, чтобы проверить, все ли листья
находятся на том же уровне. В основном использует checkUtil () * /

public virtual bool check(Node node)

{

    int level = 0;

    return checkUtil(node, level, mylevel);

}

  
// Код драйвера

public static void Main(string[] args)

{

    // Давайте создадим дерево, как показано в примере

    GFG tree = new GFG();

    tree.root = new Node(12);

    tree.root.left = new Node(5);

    tree.root.left.left = new Node(3);

    tree.root.left.right = new Node(9);

    tree.root.left.left.left = new Node(1);

    tree.root.left.right.left = new Node(1);

    if (tree.check(tree.root))

    {

        Console.WriteLine("Leaves are at same level");

    }

    else

    {

        Console.WriteLine("Leaves are not at same level");

    }

}
}

  
// Этот код предоставлен Shrikant13


Выход:

Leaves are at same level

Сложность времени: функция выполняет простой обход дерева, поэтому сложность равна O (n).

Метод 1 (итеративный)

Это также может быть решено с помощью итеративного подхода.

Идея состоит в том, чтобы итеративно пройти по дереву, и когда вы встретите первый листовой узел, сохраните его уровень в переменной результата, теперь, когда вы сталкиваетесь с каким-либо листовым узлом, сравнивайте его уровень с ранее сохраненным результатом, если они совпадают, то продолжайте до конца дерево, иначе вернуть ложь.

C ++

// Программа CPP, чтобы проверить, все ли конечные узлы находятся в
// тот же уровень двоичного дерева
#include <bits/stdc++.h>

using namespace std;

   
// узел дерева

struct Node {

    int data;

    Node *left, *right;

};

   
// возвращает новый узел дерева

Node* newNode(int data)

{

    Node* temp = new Node();

    temp->data = data;

    temp->left = temp->right = NULL;

    return temp;

}

   
// возвращаем true, если все конечные узлы
// на том же уровне, иначе ложь

int checkLevelLeafNode(Node* root)

{

    if (!root)

        return 1;

   

    // создаем очередь для прохождения порядка уровней

    queue<Node*> q;

    q.push(root);

   

    int result = INT_MAX;

     int level = 0;

  

    // пройти до тех пор, пока очередь не опустеет

    while (!q.empty()) {

        int size = q.size();

        level += 1;

  

        // пройти полный уровень

        while(size > 0){

            Node* temp = q.front();

            q.pop();

          

            // проверка левого ребенка

            if (temp->left) {

                q.push(temp->left);

  

                // если его листовой узел

                if(!temp->left->right && !temp->left->left){

  

                    // если это первый листовой узел, то обновить результат

                    if (result == INT_MAX)

                        result = level;

                      

                    // если это не первый листовой узел, тогда сравниваем

                    // уровень с уровнем предыдущего конечного узла

                    else if (result != level)

                        return 0;                    

                }

            }

               

             // проверка на правильность ребенка

            if (temp->right){

                q.push(temp->right);

  

                // если это листовой узел

                if (!temp->right->left && !temp->right->right)

  

                    // если это первый листовой узел до сих пор,

                    // затем обновляем результат

                    if (result == INT_MAX)

                        result = level;

                      

                    // если это не первый листовой узел,

                    // затем сравниваем уровень с уровнем

                    // предыдущего листового узла

                    else if(result != level)

                        return 0;

                      

               }

               size -= 1;

        }    

    }

      

    return 1;

}

   
// драйверная программа

int main()

{

    // построить дерево

    Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->right = newNode(4);

    root->right->left = newNode(5);

    root->right->right = newNode(6);

   

    int result = checkLevelLeafNode(root);

    if (result)

        cout << "All leaf nodes are at same level\n";

    else

        cout << "Leaf nodes not at same level\n";

    return 0;

}

Джава

// Java-программа для проверки, все ли конечные узлы находятся в
// тот же уровень двоичного дерева

import java.util.*;

  
// Пользовательский класс узла

class Node {

      int data;

      Node left, right;

        

      // Конструктор для создания нового узла дерева

      Node(int key) {

           int data = key;

           left = right = null;

      }

}

  

class GFG {

  

      // возвращаем true, если все конечные узлы

      // на том же уровне, иначе ложь

      static boolean checkLevelLeafNode(Node root)

      {

             if (root == null)

                 return true;

  

             // создаем очередь для прохождения порядка уровней

             Queue<Node> q = new LinkedList<>();

             q.add(root);

           

             int result = Integer.MAX_VALUE;

             int level = 0;

  

             // пройти до тех пор, пока очередь не опустеет

             while (q.size() != 0) {

                    int size = q.size();

                    level++;

  

                    // пройти полный уровень

                    while (size > 0) {

                         Node temp = q.remove();

  

                         // проверка левого ребенка

                         if (temp.left != null) {

                             q.add(temp.left);

  

                              // если его листовой узел

                              if (temp.left.left == null && temp.left.right == null) {

                                   

                                  // если это первый листовой узел, то обновить результат

                                  if (result == Integer.MAX_VALUE)

                                      result = level;

  

                                  // если это не первый листовой узел, тогда сравниваем

                                  // уровень с уровнем предыдущего конечного узла.

                                  else if (result != level)

                                       return false

                              }

                         }

                           

                          // проверка на правильность ребенка

                          if (temp.right != null) {

                             q.add(temp.right);

  

                              // если его листовой узел

                             if (temp.right.left == null && temp.right.right == null) {

                                   

                                  // если это первый листовой узел, то обновить результат

                                  if (result == Integer.MAX_VALUE)

                                      result = level;

  

                                  // если это не первый листовой узел, тогда сравниваем

                                  // уровень с уровнем предыдущего конечного узла.

                                  else if (result != level)

                                       return false

                              }

                         }

                         size--;

                    }

  

             }

             return true;

      }

  

      // Код драйвера

      public static void main(String args[])

      {

             // построить дерево

             Node root = new Node(1);

             root.left = new Node(2);

             root.right = new Node(3);

             root.left.right = new Node(4);

             root.right.left = new Node(5);

             root.right.right = new Node(6);

  

             boolean result = checkLevelLeafNode(root);

             if (result == true)

                 System.out.println("All leaf nodes are at same level");

             else

                 System.out.println("Leaf nodes not at same level");  

      }

}
// Этот код предоставлен rachana soma

python3

# Python3 программа для проверки, все ли конечные узлы
# находятся на одном уровне двоичного дерева

INT_MAX = 2**31

INT_MIN = -2**31

  
# Tree Node
# возвращает новый узел дерева

class newNode: 

    def __init__(self, data): 

        self.data = data 

        self.left = self.right = None

          
# вернуть true, если все конечные узлы
# на том же уровне, иначе ложь

def checkLevelLeafNode(root) :

  

    if (not root) :

        return 1

      

    # создать очередь для уровня

    # обход заказа

    q = [] 

    q.append(root) 

      

    result = INT_MAX 

    level = 0

  

    # ход, пока очередь не пуста

    while (len(q)):

        size = len(q) 

        level += 1

  

        # ход за полный уровень

        while(size > 0 or len(q)): 

            temp = q[0

            q.pop(0

          

            # проверить левого ребенка

            if (temp.left) :

                q.append(temp.left) 

  

                # если его листовой узел

                if(not temp.left.right and 

                   not temp.left.left): 

  

                    # если это первый листовой узел,

                    # затем обновите результат

                    if (result == INT_MAX):

                        result = level 

                      

                    # если это не первый листовой узел,

                    # затем сравните уровень с

                    # уровень предыдущего листового узла

                    elif (result != level): 

                        return 0                    

                  

            # проверить правильность ребенка

            if (temp.right) :

                q.append(temp.right) 

  

                # если это листовой узел

                if (not temp.right.left and 

                    not temp.right.right): 

  

                    # если это первый листовой узел до сих пор,

                    # затем обновите результат

                    if (result == INT_MAX): 

                        result = level 

                      

                    # если это не первый листовой узел,

                    # затем сравните уровень с уровнем

                    № предыдущего листового узла

                    elif(result != level): 

                        return 0

                size -= 1

    return 1

  
Код водителя

if __name__ == '__main__':

      

    # построить дерево

    root = newNode(1

    root.left = newNode(2

    root.right = newNode(3

    root.left.right = newNode(4

    root.right.left = newNode(5

    root.right.right = newNode(6

      

    result = checkLevelLeafNode(root) 

    if (result) :

        print("All leaf nodes are at same level")

    else:

        print("Leaf nodes not at same level")

  
# Этот код предоставлен SHUBHAMSINGH10

C #

// C # программа для проверки, все ли конечные узлы находятся в
// тот же уровень двоичного дерева

using System;

using System.Collections.Generic;

  
// Пользовательский класс узла

public class Node

    public int data; 

    public Node left, right; 

          

    // Конструктор для создания нового узла дерева

    public Node(int key) 

    

        int data = key; 

        left = right = null

    

  

public class GFG 

  

    // возвращаем true, если все конечные узлы

    // на том же уровне, иначе ложь

    static bool checkLevelLeafNode(Node root) 

    

            if (root == null

                return true

  

            // создаем очередь для прохождения порядка уровней

            Queue<Node> q = new Queue<Node>(); 

            q.Enqueue(root); 

          

            int result = int.MaxValue; 

            int level = 0; 

  

            // пройти до тех пор, пока очередь не опустеет

            while (q.Count != 0) 

            

                    int size = q.Count; 

                    level++; 

  

                    // пройти полный уровень

                    while (size > 0)

                    

                        Node temp = q.Dequeue(); 

  

                        // проверка левого ребенка

                        if (temp.left != null

                        

                            q.Enqueue(temp.left); 

  

                            // если его листовой узел

                            if (temp.left.left != null && 

                                temp.left.right != null)

                            

                                  

                                // если это первый листовой узел, то обновить результат

                                if (result == int.MaxValue) 

                                    result = level; 

  

                                // если это не первый листовой узел, тогда сравниваем

                                // уровень с уровнем предыдущего конечного узла.

                                else if (result != level) 

                                    return false

                            

                        

                          

                        // проверка на правильность ребенка

                        if (temp.right != null)

                        

                            q.Enqueue(temp.right); 

  

                            // если его листовой узел

                            if (temp.right.left != null && 

                                temp.right.right != null

                            

                                  

                                // если это первый листовой узел, то обновить результат

                                if (result == int.MaxValue) 

                                    result = level; 

  

                                // если это не первый листовой узел, тогда сравниваем

                                // уровень с уровнем предыдущего конечного узла.

                                else if (result != level) 

                                    return false

                            

                        

                        size--; 

                    

            

            return true

    

  

    // Код драйвера

    public static void Main(String []args) 

    

        // построить дерево

        Node root = new Node(1); 

        root.left = new Node(2); 

        root.right = new Node(3); 

        root.left.right = new Node(4); 

        root.right.left = new Node(5); 

        root.right.right = new Node(6); 

  

        bool result = checkLevelLeafNode(root); 

        if (result == true

            Console.WriteLine("All leaf nodes are at same level"); 

        else

            Console.WriteLine("Leaf nodes not at same level"); 

    

  
// Этот код предоставлен 29AjayKumar


Выход:

All leaf nodes are at same level

Сложность времени: O (n)

Этот код предоставлен Mandeep Singh

Эта статья предоставлена Чандрой Пракаш . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Проверьте, все ли листья на одном уровне

0.00 (0%) 0 votes