Рубрики

Найти глубину самого глубокого нечетного уровня листьев узла

Напишите код, чтобы получить глубину самого глубокого нечетного листового узла уровня в двоичном дереве. Считайте, что уровень начинается с 1. Глубина листового узла — это количество узлов на пути от корня к листу (включая как лист, так и корень).

Например, рассмотрим следующее дерево. Самым глубоким узлом нечетного уровня является узел со значением 9, а глубина этого узла равна 5.

       1
     /   \
    2     3
  /      /  \  
 4      5    6
        \     \
         7     8
        /       \
       9         10
                 /
                11

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

C ++

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

using namespace std;

  
// Полезная функция для поиска
// максимум двух целых

int max(int x, int y) 

    return (x > y)? x : y; 

}

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

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;

}

  
// Рекурсивная функция для определения глубины
// самый глубокий нечетный лист уровня

int depthOfOddLeafUtil(struct Node *root,

                               int level)

{

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

    if (root == NULL)

        return 0;

  

    // Если этот узел лист и его уровень

    // странно, вернуть его уровень

    if (root->left == NULL && 

        root->right == NULL && level & 1)

        return level;

  

    // Если не лист, вернуть максимальное значение

    // из левого и правого поддерева

    return max(depthOfOddLeafUtil(root->left, level + 1),

               depthOfOddLeafUtil(root->right, level + 1));

}

  
/ * Основная функция, которая вычисляет глубину

   самого глубокого нечетного уровня листа. Эта функция

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

int depthOfOddLeaf(struct Node *root)

{

    int level = 1, depth = 0;

    return depthOfOddLeafUtil(root, level);

}

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

int main()

{

    struct Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

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

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

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

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

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

  

    cout << depthOfOddLeaf(root) 

         << " is the required depth";

    getchar();

    return 0;

}

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

С

// Программа на C, чтобы найти глубину самого глубокого нечетного листового узла уровня
#include <stdio.h>
#include <stdlib.h>

  
// Полезная функция для поиска максимум двух целых чисел

int max(int x, int y) { return (x > y)? x : y; }

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

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;

}

  
// Рекурсивная функция для определения глубины самого глубокого нечетного листа уровня

int depthOfOddLeafUtil(struct Node *root,int level)

{

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

    if (root == NULL)

        return 0;

  

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

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

        return level;

  

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

    return max(depthOfOddLeafUtil(root->left, level+1),

            depthOfOddLeafUtil(root->right, level+1));

}

  
/ * Основная функция, которая вычисляет глубину самого глубокого листа нечетного уровня.
Эта функция в основном использует deepOfOddLeafUtil () * /

int depthOfOddLeaf(struct Node *root)

{

    int level = 1, depth = 0;

    return depthOfOddLeafUtil(root, level);

}

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

int main()

{

    struct Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

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

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

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

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

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

  

    printf("%d is the required depth\n", depthOfOddLeaf(root));

    getchar();

    return 0;

}

Джава

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

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    // Рекурсивная функция для определения глубины самого глубокого нечетного листа уровня

    int depthOfOddLeafUtil(Node node, int level) 

    {

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

        if (node == null)

            return 0;

   

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

        if (node.left == null && node.right == null && (level & 1) != 0)

            return level;

   

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

        return Math.max(depthOfOddLeafUtil(node.left, level + 1),

                depthOfOddLeafUtil(node.right, level + 1));

    }

   

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

       Эта функция в основном использует deepOfOddLeafUtil () * /

    int depthOfOddLeaf(Node node) 

    {

        int level = 1, depth = 0;

        return depthOfOddLeafUtil(node, level);

    }

   

    public static void main(String args[]) 

    {

        int k = 45;

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

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

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

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

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

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

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

        tree.root.right.right.right = new Node(8);

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

        tree.root.right.right.right.right = new Node(10);

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

        System.out.println(tree.depthOfOddLeaf(tree.root) + 

                                                   " is the required depth");

    }

}

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

питон

# Программа Python, чтобы найти глубину самого глубокого нечетного уровня
# листовой узел

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

class Node:

      

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Рекурсивная функция для поиска глубины самого глубокого
# нечетный листовой узел уровня

def depthOfOddLeafUtil(root, level):

      

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

    if root is None:

        return 0 

  

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

    # его уровень

    if root.left is None and root.right is None and level&1

        return level 

      

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

    # и правильные поддеревья

    return (max(depthOfOddLeafUtil(root.left, level+1),

                depthOfOddLeafUtil(root.right, level+1)))

  
# Основная функция, которая вычисляет глубину самого глубокого нечетного
# лист уровня.
# Эта функция в основном использует глубинуOfOddLeafUtil ()

def depthOfOddLeaf(root):

    level = 1 

    depth = 0

    return depthOfOddLeafUtil(root, level)

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

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.right.left = Node(5)

root.right.right = Node(6)

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

root.right.right.right = Node(8)

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

root.right.right.right.right = Node(10)

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

  

print "%d is the required depth" %(depthOfOddLeaf(root))

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

C #

using System;

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

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

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    public Node root;

  

    // Рекурсивная функция для определения глубины самого глубокого нечетного листа уровня

    public virtual int depthOfOddLeafUtil(Node node, int level)

    {

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

        if (node == null)

        {

            return 0;

        }

  

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

        if (node.left == null && node.right == null && (level & 1) != 0)

        {

            return level;

        }

  

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

        return Math.Max(depthOfOddLeafUtil(node.left, level + 1),

                        depthOfOddLeafUtil(node.right, level + 1));

    }

  

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

    Эта функция в основном использует deepOfOddLeafUtil () * /

    public virtual int depthOfOddLeaf(Node node)

    {

        int level = 1, depth = 0;

        return depthOfOddLeafUtil(node, level);

    }

  

    public static void Main(string[] args)

    {

        int k = 45;

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

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

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

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

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

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

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

        tree.root.right.right.right = new Node(8);

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

        tree.root.right.right.right.right = new Node(10);

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

        Console.WriteLine(tree.depthOfOddLeaf(tree.root) + " is the required depth");

    }

}

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


Выход:

5 is the required depth

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

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

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;

}

  
// вернуть максимальное нечетное число
// глубина листового узла

int maxOddLevelDepth(Node* root)

{

    if (!root)

        return 0;

  

    // создаем очередь

    // для уровня порядка

    // обход

    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 && !temp->right 

                      && (level % 2 != 0))

            {

                result = level;

            }

          

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

            if (temp->left) 

            {

                q.push(temp->left);

            }

              

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

            if (temp->right)

            {

                q.push(temp->right);

            }

            size -= 1;

        

    }

      

    return result;

}

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

int main()

{

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

    Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

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

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

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

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

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

  

    int result = maxOddLevelDepth(root);

      

    if (result == INT_MAX)

        cout << "No leaf node at odd level\n";

    else

        cout << result;

        cout << " is the required depth " << endl;

    return 0;

}

Джава

// Java-программа для поиска глубины
// лист нечетного уровня двоичного дерева

import java.util.*;

  

class GFG 

{

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

static class Node 

{

    int data;

    Node left, right;

};

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

static Node newNode(int data)

{

    Node temp = new Node();

    temp.data = data;

    temp.left = temp.right = null;

    return temp;

}

  
// возвращаем максимальную глубину нечетного числа листового узла

static int maxOddLevelDepth(Node root)

{

    if (root == null)

        return 0;

  

    // создаем очередь по уровню порядка

    // обход

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

    q.add(root);

  

    int result = Integer.MAX_VALUE;

    int level = 0;

  

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

    while (!q.isEmpty()) 

    {

        int size = q.size();

        level += 1;

  

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

        while(size > 0)

        {

            Node temp = q.peek();

            q.remove();

  

            // проверяем, является ли узел листовым и

            // уровень нечетный, если уровень нечетный,

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

            if(temp.left == null && 

               temp.right == null && (level % 2 != 0))

            {

                result = level;

            }

          

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

            if (temp.left != null

            {

                q.add(temp.left);

            }

              

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

            if (temp.right != null)

            {

                q.add(temp.right);

            }

            size -= 1;

        

    }

    return result;

}

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

public static void main(String[] args)

{

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

    Node root = newNode(1);

    root.left = newNode(2);

    root.right = newNode(3);

    root.left.left = newNode(4);

    root.right.left = newNode(5);

    root.right.right = newNode(6);

    root.right.left.right = newNode(7);

    root.right.right.right = newNode(8);

    root.right.left.right.left = newNode(9);

    root.right.right.right.right = newNode(10);

    root.right.right.right.right.left = newNode(11);

  

    int result = maxOddLevelDepth(root);

      

    if (result == Integer.MAX_VALUE)

        System.out.println("No leaf node at odd level");

    else

    {

        System.out.print(result);

        System.out.println(" is the required depth ");

    }

}
}

  
// Этот код предоставлен Rajput-Ji

python3

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

  

INT_MAX = 2**31

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

class newNode: 

    def __init__(self, data): 

        self.data = data 

        self.left = self.right = None

          
# вернуть максимальную глубину нечетного числа
№ листового узла

def maxOddLevelDepth(root) :

  

    if (not root): 

        return 0

  

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

    # обход

    q = [] 

    q.append(root) 

  

    result = INT_MAX 

    level = 0

  

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

    while (len(q)) :

      

        size = len(q) 

        level += 1

  

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

        while(size > 0) :

          

            temp = q[0

            q.pop(0

  

            # проверить, является ли узел листовым узлом

            # и уровень нечетный, если уровень

            # нечетный, тогда обновите результат

            if(not temp.left and not temp.right 

                    and (level % 2 != 0)) :

              

                result = level 

              

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

            if (temp.left) :

              

                q.append(temp.left) 

              

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

            if (temp.right) :

              

                q.append(temp.right) 

              

            size -= 1

      

    return result 

  
Код водителя

if __name__ == '__main__':

    root = newNode(1

    root.left = newNode(2

    root.right = newNode(3

    root.left.left = newNode(4

    root.right.left = newNode(5

    root.right.right = newNode(6

    root.right.left.right = newNode(7

    root.right.right.right = newNode(8

    root.right.left.right.left = newNode(9

    root.right.right.right.right = newNode(10

    root.right.right.right.right.left = newNode(11

  

    result = maxOddLevelDepth(root) 

    if (result == INT_MAX) :

        print("No leaf node at odd level"

    else:

        print(result, end = "")

        print(" is the required depth ")

          
# Этот код добавлен
# от SHUBHAMSINGH10

C #

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

using System;

using System.Collections.Generic;

      

class GFG 

{

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

public class Node 

{

    public int data;

    public Node left, right;

};

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

static Node newNode(int data)

{

    Node temp = new Node();

    temp.data = data;

    temp.left = temp.right = null;

    return temp;

}

  
// возвращаем максимальную глубину нечетного числа листового узла

static int maxOddLevelDepth(Node root)

{

    if (root == null)

        return 0;

  

    // создаем очередь по уровню порядка

    // обход

    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 += 1;

  

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

        while(size > 0)

        {

            Node temp = q.Peek();

            q.Dequeue();

  

            // проверяем, является ли узел листовым и

            // уровень нечетный, если уровень нечетный,

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

            if(temp.left == null && 

               temp.right == null &&

              (level % 2 != 0))

            {

                result = level;

            }

          

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

            if (temp.left != null

            {

                q.Enqueue(temp.left);

            }

              

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

            if (temp.right != null)

            {

                q.Enqueue(temp.right);

            }

            size -= 1;

        

    }

    return result;

}

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

public static void Main(String[] args)

{

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

    Node root = newNode(1);

    root.left = newNode(2);

    root.right = newNode(3);

    root.left.left = newNode(4);

    root.right.left = newNode(5);

    root.right.right = newNode(6);

    root.right.left.right = newNode(7);

    root.right.right.right = newNode(8);

    root.right.left.right.left = newNode(9);

    root.right.right.right.right = newNode(10);

    root.right.right.right.right.left = newNode(11);

  

    int result = maxOddLevelDepth(root);

      

    if (result == int.MaxValue)

        Console.WriteLine("No leaf node at odd level");

    else

    {

        Console.Write(result);

        Console.WriteLine(" is the required depth ");

    }

}
}

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

Выход:

5 is the required depth

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

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

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

Найти глубину самого глубокого нечетного уровня листьев узла

0.00 (0%) 0 votes