İkili Ağac Leetcode həllinin maksimum dərinliyi

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon Facebook microsoft
alqoritmlər İkili ağac kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions Recursion Ağacın keçidiBaxılıb 37

Problem bəyanat

Problemdə a ikili ağac verilmişdir və verilmiş ağacın maksimum dərinliyini öyrənməliyik. İkili ağacın maksimum dərinliyi kök düyünündən ən uzaq yarpaq düyününə qədər ən uzun yol boyunca qovşaqların sayıdır.

misal

 
  3
 / \
9   20
   /  \		 
  15   7
3

İzahat: Aşağıdakı ağacda qırmızı rəngdə göstərildiyi kimi iki mümkün ən uzun yol var.
İkili Ağac Leetcode həllinin maksimum dərinliyi

Empty Tree
0

Ağac boş olduğundan dərinlik 0-dir.

0
1

Yalnız bir qovşaq olduğundan dərinlik 1-dir.

Yanaşma

Ağacın maksimum dərinliyini tapmaq üçün sadə bir rekursiv yanaşma tətbiq edə bilərik. Hər bir funksiya çağırışı 'kök' adlanan kök düyünü olan bir alt ağacı təmsil edəcəkdir. Kök düyündən başlayaraq rekursiv bir funksiya ilə ağacdan keçirik.

Beləliklə, əsas vəziyyət alt ağacın boş olmasıdır, yəni kök NULL-dur. Beləliklə, dərinliyi 0 olaraq qaytarırıq.

kök NULL deyilsə, eyni funksiyanı sol uşağı və sağ uşağı üçün rekursiv olaraq çağırın.

Şəkildə göstərildiyi kimi, iki uşaq funksiyası dərinliyini qaytardıqda, bu iki alt ağacdan maksimumu seçirik və 1-i əlavə etdikdən sonra bu dəyəri qaytarırıq (İki alt ağacın ana hissəsi olan cari düyün əlavə olunur).

İkili Ağacın Maksimum DərinliyiPin

Həyata keçirilməsi

İkili Ağac Leetcode həllinin maksimum dərinliyi üçün C ++ proqramı

#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

İkili Ağac Leetcode Həllinin Maksimum Dərinliyi üçün Java Proqramı

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

İkili Ağac Leetcode həllinin maksimum dərinliyi üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (N):  hər bir nodu dəqiq bir dəfə ziyarət edirik, beləliklə zaman mürəkkəbliyi O (N) -dir, burada N verilən ağacdakı qovşaqların ümumi sayıdır.

Kosmik Mürəkkəblik 

O (N):  Ən pis vəziyyətdə, ağac tamamilə balanssızdır, məsələn, hər bir qovşaqda yalnız sol uşaq düyünü və ya yalnız sağ uşaq düyünü var, o zaman rekursiya çağırışı N dəfə (ağacın hündürlüyü) baş verəcəkdir. Bu səbəbdən zəng yığınının maksimum ölçüsü O (N) olmalıdır.
Ən yaxşı halda (ağac tamamilə balanslaşdırılmışdır), ağacın hündürlüyü log⁡ (N) olardı. Buna görə bu vəziyyətdə kosmik mürəkkəblik O (log⁡ (N)) olardı.

Şərh yaz

Translate »
1