Binary Tree LeetCode Həllinin yarpaqlarını tapın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Atlassian Bloomberg eBay Facebook google LinkedIn microsoftBaxılıb 80

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

İkili Ağacın yarpaqlarını tapın LeetCode Həll - Nəzərə alınmaqla root bir ikili ağac, ağacın qovşaqlarını toplayın, sanki bunu edirsiniz:

  • Bütün yarpaq düyünlərini toplayın.
  • Bütün yarpaq düyünlərini çıxarın.
  • Ağac boş olana qədər təkrarlayın.

misal

Test işi 1:

Input:

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

Çıxış:

[[4, 5, 3], [2], [1]]

Binary Tree LeetCode Həllinin yarpaqlarını tapınPin

Izahat

[[3, 5, 4], [2], [1]] və [[3, 4, 5], [2], [1]] də düzgün cavablar hesab olunur, çünki hər səviyyə üçün sıra fərqi yoxdur hansı elementlərin qaytarıldığı.

Yanaşma:

Idea:

  • Sol alt ağacdan yarpaqları və yenilənmiş kökləri toplayın.
  • Sağ alt ağacdan yarpaqları və yenilənmiş kökləri toplayın
  • Hər iki nəticə əsasında yarpaqları toplayın və hər iki nəticədən istifadə edərək kökü yeniləyin, toplanmış yarpaqları və yeni yenilənmiş kökləri rekursiyada yuxarıya göndərin.
  • Rekursiya funksiyasının əsas şərti belə olacaq, əgər göstərilən kök yarpaqdırsa, siyahını tək elementlə qaytarın root.val və kök null olaraq yeniləndi
  • Əsas funksiyada kök sıfır olana qədər kök üzərində təkrarlayın.

Bu, bir DFS həll. İkili ağac tək istiqamətli ağacdır. Onun uşaqlarını silmək üçün siz ana qovşağın məlumatını saxlamalısınız (onun sol və ya sağ nodu null olaraq təyin etmək üçün). Beləliklə, bu həllin iki addımı var:

  1. Hansı nodu tapın node.left == null && node.right == null.
  2. Valideynlərinə de ki, yarpaqları silsinlər. Mənim həllimdə mən ana qovşağına uşaq qovşağının silinib-silinməyəcəyini bildirmək üçün boolean dəyəri qaytarmaq üçün istifadə edirəm. Digər həllər üçün siz rekursiv DFS çağırışı ilə valideyni ötürə bilərsiniz.

qovşağın hündürlüyü düyünü çıxardığımız dəyirmi olsun. (məsələn, bütün yarpaqların hündürlüyü 0-dır). biz hər bir düyünün hündürlüyünü yalnız yarpağa çatdıqda və geri qayıtdıqda bilə bilərik.

Ona görə də yarpaqdan anasına qayıtdığımız zaman yarpaqları yığıb müvafiq siyahıya salırıq. Qeyd edək ki, valideynin boyu onun uşaqlarının maksimum boyu + 1-ə bərabərdir.

İkili ağacın yarpaqlarını tapmaq üçün kod

Java Proqramı

/**
 * Definition for a binary tree node.
 * public 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 Solution {
    private boolean removeLeaves(TreeNode root, List<Integer> layer) {
        if (root == null) return false;
        if (root.left == null && root.right == null) {
            layer.add(root.val);
            return true;
        }
        if (removeLeaves(root.left, layer)) {
            root.left = null;
        }
        if (removeLeaves(root.right, layer)) {
            root.right = null;
        }
        return false;
    }
    
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        while (root != null) {
            List<Integer> layer = new ArrayList<>();
            if (removeLeaves(root, layer)) {
                root = null;
            }
            res.add(layer);
        }
        return res;
    }
}

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:
    int getLeaves(vector<int>&temp, TreeNode* root){
        if(root == nullptr) return 0;
        int left = getLeaves(temp,root->left);
        int right = getLeaves(temp,root->right);
        if(left == 0 && right == 0){
            temp.push_back(root->val);
            return -1;
        }
        if(left == -1) root->left = nullptr;
        if(right == -1) root->right = nullptr;
        return 1;
    }
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>>res;
        while(root && (root->left || root->right)){
            vector<int>temp;
            getLeaves(temp,root);
            res.push_back(temp);
        }
        res.push_back({root->val});
        return res;
    }
};

Binary Tree LeetCode Həllinin yarpaqlarını tapmaq üçün mürəkkəblik təhlili

zaman mürəkkəbliyi: 2N = O(N)

kosmik mürəkkəblik: O (N)

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