Максимальная глубина двоичного дерева


Сложный уровень Легко
Часто спрашивают в Амазонка Cadence Индия Купон Набор фактов Свободный заряд MakeMyTrip Монотипные решения Snapdeal Synopsys Teradata VMware Zoho
Поиск в глубину дерево Обход дерева

Постановка задачи

Проблема «Максимальная глубина двоичного дерева» заключается в том, что вам дана структура данных двоичного дерева. Выведите максимальную глубину заданного бинарное дерево.

Пример

вход

Максимальная глубина двоичного дерева

2

Объяснение: Максимальная глубина для данного дерева равна 2. Потому что есть только один элемент ниже корня (т. Е. На большей глубине, чем корневой уровень = 1) как в левом, так и в правом поддереве.

вход

Максимальная глубина двоичного дерева

3

Объяснение: На уровне 3 в правом поддереве есть два элемента. Таким образом, максимальная глубина = 3.

Алгоритм максимальной глубины двоичного дерева

1. Initialize a binary tree data structure.
2. Create a class node with a variable of integer type and the two-node type pointers left and right as it's private members.
3. Create a function newNode to create a new node of the binary tree which accepts a variable of integer type consisting of data as it's a parameter.
4. After that, initialize a new node inside it. Store the integer variable given as a parameter in the data of the node of the binary tree and update the value of it's left and the right pointer is null.
5. Return the newly created node.
6. Similarly, create a function to find the maximum depth of the binary tree which accepts a node pointer as it's a parameter.
7. Check if the node is equal to null, return 0.
8. Else create a variable left of integer type representing the depth of the left subtree. Make a recursive call to the function itself with the left of the node as it's a parameter and store the result returned in the variable left.
9. Similarly, create a variable right of integer type representing the depth of the right subtree. Make a recursive call to the function itself with the right of the node as it's a parameter and store the result returned in the variable right.
10. After that, check if the depth of the left subtree is greater than the depth of the right subtree return the depth of the left subtree + 1.
11. Else return the variable right i.e. the depth of the right subtree + 1.

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

Для определения максимальной глубины мы вычисляем глубину левого и правого поддерева. Глубина текущего дерева равна максимуму левого и правого поддерева +1. Таким образом, мы используем рекурсивный подход, чтобы найти глубину левого и правого поддерева. Поскольку мы используем рекурсию, у нас должны быть некоторые базовые случаи. Здесь базовый случай - если мы находимся в узле, который является листом. Листовой узел имеет длину = 1.

Код:

Программа на C ++ для поиска максимальной глубины двоичного дерева

#include <bits/stdc++.h> 
using namespace std; 
  
class node{  
    public: 
        int data;  
        node* left;  
        node* right;  
};  
  
int maxDepth(node* node){  
    if(node == NULL)  
        return 0;  
    else{  
        int left = maxDepth(node->left);  
        int right = maxDepth(node->right);  
      
        if(left > right)  
            return(left + 1);  
        else return(right + 1);  
    }  
}  
  
node* newNode(int data){  
    node* Node = new node(); 
    Node->data = data;  
    Node->left = NULL;  
    Node->right = NULL;  
      
    return(Node);  
}  
      
int main(){  
    node *root = newNode(2);  
  
    root->left = newNode(3);  
    root->right = newNode(8);  
    root->left->left = newNode(6);  
    root->left->right = newNode(9);  
      
    cout<<maxDepth(root);  
    return 0;  
}
3

Программа на Java для поиска максимальной глубины двоичного дерева

class Node{ 
    int data; 
    Node left, right; 
   
    Node(int item){ 
        data = item; 
        left = right = null; 
    } 
} 
   
class BinaryTree{ 
     Node root; 
   
    int maxDepth(Node node){ 
        if(node == null) 
            return 0; 
        else{ 
            int left = maxDepth(node.left); 
            int right = maxDepth(node.right); 
   
            if(left > right) 
                return (left + 1); 
             else 
                return (right + 1); 
        } 
    } 
       
    public static void main(String[] args){ 
        BinaryTree tree = new BinaryTree(); 
   
        tree.root = new Node(2); 
        tree.root.left = new Node(3); 
        tree.root.right = new Node(8); 
        tree.root.left.left = new Node(6); 
        tree.root.left.right = new Node(9); 
   
        System.out.println(tree.maxDepth(tree.root)); 
    } 
}
3

Анализ сложности

Сложность времени

НА) где n - количество узлов данных, вставленных в данное двоичное дерево.

Космическая сложность

O (1) потому что мы использовали постоянное дополнительное пространство.

дело