Binary Tree Sağ Yan Görünüş LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Çiy kərpic Amazon alma Bloomberg ByteDance Qapılar eBay Facebook Məlumat dəsti Goldman Sachs google microsoft Kahin PayPal Über VMware
Walmart Qlobal texnologiyaBaxılıb 68

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

Binary Tree Sağ Yan Görünüş LeetCode Həlli – Nəzərə alınmaqla root ikili ağacın üzərində dayandığınızı təsəvvür edin sağ tərəf ondan və qayıt görə biləcəyiniz qovşaqların dəyərləri yuxarıdan aşağıya sıralanır.

misal

Test işi 1:

Input:

kök = [1, 2, 3, null, 5, null, 4]

Çıxış:

[1, 3, 4]

Binary Tree Sağ Yan Görünüş LeetCode HəlliPin

Yanaşma:

Ağacın keçidi ilə bağlı problem adətən a deməkdir genişlik ilk axtarış və ya dərinlik ilk axtarış yanaşma. Hər səviyyədən bir dəyəri təcrid etmək tapşırığımız olduğundan, bu, təbii olaraq BFS yanaşmasını yada salacaq... lakin gəlin DFS-ni arxa planda saxlayaq; ona qayıdacağıq.

BFS yanaşması adətən növbənin istifadəsini nəzərdə tutur (q) biz hər bir node uşaqları üzərinə itələyirik q biz ağacın bir səviyyəsindən bir tərəfdən digərinə hərəkət edərkən. Bu, hər səviyyəni tamamladıqdan sonra növbəti səviyyəyə keçməyə hazır olduğumuzu təmin edir q. Hər səviyyəni ayırmaq üçün, çünki biz davamlı olaraq əlavə edirik q, yalnız uzunluğunu götürə bilərik q növbəti birinin nə vaxt başladığını anlamaq üçün hər səviyyənin əvvəlində.

Bu halda, biz BFS-ni sağdan sola işlədə bilərik və sadəcə olaraq cavab massivimizdə hər səviyyənin ilk dəyərini itələyə bilərik (iləvvəl) dönən ağacın tam keçidindən sonra massiv.

Bəs DFS yanaşması haqqında nə demək olar? DFS həllər tez-tez bizə qısa tapmağa imkan verir, rekursiv həlli və səviyyənin vacib olduğu ağacların keçməsi problemlərinə gəldikdə, onlar həmişə ilk fikir olmasa da, bu halda bütövlükdə səviyyəyə ehtiyacımız yoxdur, sadəcə olaraq hər səviyyənin bir ucuna ehtiyacımız var.

Bu o deməkdir ki, biz rekursiv funksiya təyin edə bilərik (DFS) qovşaqlar arasında soldan sağa keçmək və sadəcə olaraq hər səviyyə üçün dəyərin üzərinə yazmaq (ans[lvl]) hər bir qovşağa çatdıqda, hər səviyyədə soldan sağa sonuncu dəyər saxlamaq istədiyimiz dəyər olacaqdır.

addım-addım

1. int dəyərlərini saxlayan vektor elan edin
2. node növü dəyərini saxlayan növbə elan edin (TreeNode*)
3. kökü növbəyə itələyin
4. növbə boş qalmayana qədər işləyin
5. növbədə mövcud olan sonuncu elementə qədər təkrarlayın və cari növbə ölçüsünün sonuncu elementini itələyin
6. null olub-olmadığını sol və sağ node yoxlayın
7. 4-dən 6-a qədər olan addımları təkrarlayın
8. vektoru qaytarın.

İkili Ağacın Sağ Yan Görünüşü üçün Kod

C ++ Proqramı

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root) {
            return {};
        }
        vector<int> v; //store values of nodes in the rightmost
        queue<TreeNode*> Q; //store node type values in queue 
        Q.push(root); //push root
        while(!Q.empty()) { //repeat steps until queue is not empty
            
            int size = Q.size();  // current size of queue
            for(int i = 0; i < size; i++) {
              TreeNode* t = Q.front(); //declare a temp node and put front node of queue
                Q.pop(); 
                if(i==size-1) {   //if node is rightmost 
                    v.push_back(t->val); //push the value of rightmost node into vector
                }
                if(t->left) {   //if temp->left != NULL then push into queue
                    Q.push(t->left);
                }
                if(t->right) { //if temp->right != NULL then push into queue
                    Q.push(t->right);
                }
            }  
        }
        return v; //finally we have all values
    }
};

Python proqramı

from collections import deque
class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        right_v, q = [], deque()
        if root:
            q.append(root)
        while len(q):
            right_v.append(q[-1].val)
            for i in range(len(q)):
                top = q.popleft()
                if top.left:
                    q.append(top.left)
                if top.right:
                    q.append(top.right)
        return right_v

Binary Tree Sağ Yan Görünüş üçün Mürəkkəblik Təhlili LeetCode Həlli

Zamanın mürəkkəbliyi: O (n)

Kosmik Mürəkkəblik: O(n) növbəyə görə

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