Максимална длабочина на решение за летен код на бинарно дрво


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Facebook Мајкрософт
Бинарно дрво Рекурзија Преминување на дрвото

Изјава за проблем

Во проблемот а бинарно дрво е даден и треба да ја откриеме максималната длабочина на даденото дрво. Максималната длабочина на бинарното дрво е бројот на јазли по најдолгата патека од коренскиот јазол надолу до најоддалечениот јазол на листот.

пример

 
  3
 / \
9   20
   /  \		 
  15   7
3

Објаснување: Постојат две можни најдолги патеки како што е прикажано на подолу дрвото во црвена боја.
Максимална длабочина на решение за летен код на бинарно дрво

Empty Tree
0

Бидејќи дрвото е празно, длабочината е 0.

0
1

Бидејќи има само еден јазол, длабочината е 1.

Пристап

За да ја пронајдеме максималната длабочина на дрвото, можеме да примениме едноставен рекурзивен пристап. Каде што секој повик за функција ќе претставува поддрево кое има коренски јазол наречен „root“. Ние го поминуваме дрвото со рекурзивна функција, почнувајќи од коренскиот јазол.

Значи, основниот случај е кога под-дрвото е празно, т.е. коренот е NULL. Значи, ја враќаме длабочината како 0.

ако root не е NULL, повикајте ја истата функција рекурзивно за нејзиното лево и десно дете.

Како што е прикажано на сликата, кога функцијата на двете деца ќе ја врати својата длабочина, ние избираме максимум од овие две подстела и ја враќаме оваа вредност откако ќе додадеме 1 на неа (Додавање на тековниот јазол што е родител на двете подстери).

Максимална длабочина на бинарно дрво

Имплементација

Програма C ++ за максимална длабочина на решение за летен код на бинарно стебло

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

int maxDepth(TreeNode* root) 
{
    if(root==NULL) return 0;
    return 1+max(maxDepth(root->left),maxDepth(root->right));
}

int main() 
{
    TreeNode *root= new TreeNode(3);
    root->left= new TreeNode(9);
    root->right= new TreeNode(20);
    root->right->left= new TreeNode(15);
    root->right->right= new TreeNode(7);
    
    cout<<maxDepth(root)<<endl; 
  return 0; 
}
3

Јава програма за максимална длабочина на решението за летен код на бинарно стебло

import java.util.*;
import java.lang.*;
class TreeNode 
{
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) 
      {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

class MaxDepth
{  
    public static int maxDepth(TreeNode root) 
    {
        if(root==null) return 0;
        
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
    
    public static void main(String args[])
    {
        TreeNode root= new TreeNode(3);
        root.left= new TreeNode(9);
        root.right= new TreeNode(20);
        root.right.left= new TreeNode(15);
        root.right.right= new TreeNode(7);
       
        System.out.println(maxDepth(root));
        
    }
}
3

Анализа на сложеност за максимална длабочина на раствор за летен код на бинарно дрво

Временска комплексност

НА) :  го посетуваме секој јазол точно еднаш, со што временската сложеност е O (N), каде што N е вкупниот број на јазли во даденото дрво.

Комплексноста на просторот 

НА) :  Во најлош случај, дрвото е целосно неурамнотежено, на пр., Секој јазол оставил само детски јазол или само десен јазол, тогаш повик за повторување би се случил N пати (висината на дрвото). Затоа, максималната големина на оџакот на повици е O (N).
Во најдобар случај (дрвото е целосно избалансирано), висината на дрвото ќе биде log⁡ (N). Затоа, вселенската комплексност во овој случај би била О (log⁡ (N).