İkili Ağac Leetcode həllində yaxşı qovşaqları sayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon microsoft
alqoritmlər İkili ağac kodlaşdırma Dərinlik İlk Axtarış müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 79

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Bu problemdə a ikili ağac kökü ilə verilir. Kökdən X-ə gedən yolda X-dən böyük bir düyün yoxdursa, ağacdakı X qovluğu yaxşı adlandırılır.

Verilən ikili ağacdakı yaxşı qovşaqların sayını qaytarmalıyıq.

misal

    3
   / \
  1   4
 /   / \
3   1   5
4

Explanation:

İkili Ağac Leetcode həllində yaxşı qovşaqları sayın

Mavi rəngli düyünlər yaxşıdır.
Kök Node (3) həmişə yaxşı bir qovşaqdır.
Düyün 4 -> (3,4) kökdən başlayan yoldakı maksimum dəyərdir.
Düyün 5 -> (3,4,5) yoldakı maksimum dəyərdir
Düyün 3 -> (3,1,3) isə yoldakı maksimum dəyərdir.

    3
   /
  3
 / \
4   2
3

Explanation:

İkili Ağac Leetcode həllində yaxşı qovşaqları sayın

Düyün 2 -> (3, 3, 2) yaxşı deyil, çünki “3” ondan yüksəkdir.

Yanaşma

Bir düyünün yaxşı olub olmadığını tapmaq üçün kökündən həmin düyünə gedən yolu keçməli və dəyərinin bu yolda maksimumdan kiçik olmadığını yoxlamalıyıq.
Yaxşı qovşaqların sayını tapmaq üçün verilən ikili ağacın hər bir qovşağı üçün belə yoxlamalıyıq. Ancaq burada bir şeyi müşahidə et,

müəyyən bir düyünün cavabını kökündən keçərək tapırıqsa, onun düyününə oradan da gedə bilərik, çünki uşaq düyününün demək olar ki, yolunu da keçmişik və bu vaxta qədər keçdiyimiz maksimum dəyərə sahibik. Hər iki uşaq düyünə köçürmək üçün maksimum cari düyün dəyəri ilə yeniləməliyik.
Beləliklə, bu, DFS və ya müəyyən bir düyünə gedəcəyimiz bir rekursiyaya bənzəyir, kökdən bu düyünə gedən yolu keçirik. Beləliklə, bu problemdə rekursiya çox kömək edəcəkdir. Addımlar:

  • Parametri olaraq iki arqumentlə rekursiv funksiya yaradın. Biri qovşağın ünvanı, ikincisi isə buraya qədər tapdığımız maksimum dəyərdir.
  • İndi müəyyən bir qovşaqda olduğumuz zaman cari düyün dəyərinin cari max-dan kiçik olub olmadığını yoxlayacağıq. Kiçik deyilsə, bu qovluğu ans-lərimizə əlavə edəcəyik və maksimum dəyəri yenilədikdən sonra uşaq qovşaqları üçün eyni funksiyanı çağırırıq.

Həyata keçirilməsi

İkili Ağac Leetcode Həllində Yaxşı Düyünlər Saymaq üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left,*right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int rec(TreeNode* root, int mx)
{
   if(!root) return 0;

    int cur=0;
    if(mx <= root->val) cur++;

    mx=max(mx,root->val);
    return rec(root->left,mx) + rec(root->right,mx) + cur;
}

int goodNodes(TreeNode* root) {

    int mx= INT_MIN;
    return rec(root,mx);
}

int main() 
{
    TreeNode* root= new TreeNode(3);
    root->left=  new TreeNode(1);
    root->right=  new TreeNode(4);
    root->left->left=  new TreeNode(3);
    root->right->left=  new TreeNode(1);
    root->right->right=  new TreeNode(5);
    
    cout<< goodNodes(root) ;
    return 0; 
}
4

İkili Ağac Leetcode həllində yaxşı qovşaqları saymaq üçün Java proqramı

class Rextester{
    
static class TreeNode {
    int val;
    TreeNode left,right;
    TreeNode(int x)  {
        val=x;
        left=null;
        right=null;
    }
}
    
    static int rec(TreeNode root, int mx)
    {
        if(root==null) return 0;
        
        int cur=0;
        if(mx <= root.val) cur++;
        
        mx = Math.max(mx,root.val);
        return rec(root.left,mx) + rec(root.right,mx) + cur;
    }
    
    public static int goodNodes(TreeNode root) 
    {     
        int mx= Integer.MIN_VALUE;
        return rec(root,mx);       
    }
    
  public static void main(String args[])
    {
        TreeNode root= new TreeNode(3);
        root.left=  new TreeNode(1);
        root.right=  new TreeNode(4);
        root.left.left=  new TreeNode(3);
        root.right.left=  new TreeNode(1);
        root.right.right=  new TreeNode(5);
        
        System.out.println( goodNodes(root) );
    }
}
4

İkili Ağac Leetcode həllində yaxşı qovşaqların sayılması üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n): burada n - verilən ikili ağacdakı ümumi qovşaq sayı. Hər nodu bir dəfə ziyarət edirik.

Kosmik Mürəkkəblik 

O (n): İstifadə olunan yer rekursiya yığınının maksimum ölçüsü olacaqdır. Ən pis halda əyilmiş ikili ağac halında O (n) ölçüsünə gedə bilər.

Crack Sistemi Dizayn Müsahibələri
Translate »
1