İkili Ağac LeetCode Həllini Seriallaşdırın və Seriyadan Çıxarın

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Citadel Qapılar eBay Facebook Goldman Sachs google LinkedIn microsoft Nutanix Nvidia Kahin Quora Snapchat Boşalmaq kvadrat Über VMware Yahoo
tiktok Walmart Qlobal texnologiyaBaxılıb 64

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 Serializasiyası və Seriyasının Silinməsi LeetCode Həlli – Seriyalaşdırma məlumat strukturunun və ya obyektin faylda və ya yaddaş buferində saxlanıla bilməsi üçün bitlər ardıcıllığına çevrilməsi prosesidir və ya sonradan yenidən qurulacaq şəbəkə bağlantısı vasitəsilə ötürülür. eyni və ya digər kompüter mühiti.

İkili ağacı seriallaşdırmaq və sıradan çıxarmaq üçün alqoritm tərtib edin. Serializasiya/serializasiya alqoritminizin necə işləməsi ilə bağlı heç bir məhdudiyyət yoxdur. Siz sadəcə olaraq əmin olmalısınız ki, ikili ağacın bir sətirdə seriallaşdırıla biləcəyini və bu sətirin orijinal ağac strukturuna seriyadan çıxarılmasını təmin etmək lazımdır.

misal

Test işi 1:

Input:

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

İkili Ağac LeetCode Həllini Seriallaşdırın və Seriyadan ÇıxarınPin

Çıxış:

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

Yanaşma:

addım-addım həll edə bilərik:

Ağacı tək simli hissəyə kodlaşdırmaq üçün:

  1. biz sadəcə ağacdan keçmək üçün əvvəlcədən sifarişdən istifadə edə bilərik
  2. Və sonra düyünü “,” ilə bir sətirdə birləşdirin ki, hər bir nodu ayıra bilək.
  3. bundan sonra nəticə əldə edə bilərik // 1,2,x,x,3,4,x,x,5

Kodlanmış məlumatı ağac hissəsinə deşifrə etmək üçün:

  1. sətri saxlamaq üçün növbədən istifadə edin ki, onu ağac halına gətirək.
  2. Şifrələnmiş məlumat ağacın hər bir düyününü ayırmaq üçün vergüllə daxil edildiyi üçün onu keçmək üçün sadəcə davam metodundan istifadə edə bilərik.
  3. Bütün qovşaqları növbəyə qoyduqdan sonra biz sadəcə olaraq rekursiyanı seriyadan çıxarmaq üçün köməkçi edirik.

Köməkçi funksiya üçün:

  1. Növbənin ön hissəsini saxlamaq üçün bir sətir yaratmalıyıq ki, hər dəfə onu çıxara bilək
  2. Uşağın NULL-i təmsil etmək üçün "x"-dən istifadə etdiyim üçün bu anda onu NULL-a qaytarmalıyıq.
  3. Bundan sonra s-in dəyərini ağaca qoymaq və dəyəri saxlamaq üçün yeni qovşaq yaratmaq üçün sətri tam ədədə köçürməliyik.
  4. Nəhayət, ağacı doldurmaq üçün yalnız sol və sağ uşağın rekursiyasını edin.

Seriallaşdırın:

  1. Biz istifadə edəcəyik əvvəlcədən sifariş məlumatları sətirdə saxlamaq üçün.
  2. Etibarlı qovşaq tapılarsa, biz onun dəyərini sətirə çeviririk və boşluq əlavə edirik, məsələn, “5” və cavab sətirimizə əlavə edirik.
  3. Etibarlı node üçün biz DFS(node->sol) və DFS(node->right) çağırırıq
  4. NULL ilə rastlaşsanız, cavab sətirimizə “#” əlavə edirik.
    Qeyd: “#” əvəzinə tam ədədlərlə ziddiyyət təşkil etməyən hər hansı digər sətir istifadə edilə bilər, məsələn, “null” və ya “$ “

Seriyadan çıxarın:

  1. Biz seriallaşdırdığımızdan bəri ön sifariş traversal, biz də eyni şəkildə Ağac düyünlərini yaratmalıyıq.
  2. Biz stringstream (və ya istringstream) istifadə edirik və onu giriş məlumatları ilə işə salırıq. O, sadəcə olaraq hər qovşaqdan sonra əlavə etdiyimiz əlavə boşluqdan istifadə edərək sətri işarələndirəcək. məsələn, “1 22 43 54 #” 5 fərqli sətirdə pozulacaq {“1”, “22”, “43”, “54”, “#” }
  3. DFS-ni stringstream ilə çağırırıq və hər dəfə ss >> dəyərindən istifadə edərək bir sətir çıxarırıq.
  4. dəyər etibarlı dəyərdirsə, biz bu dəyərlə yeni qovşaq yaradırıq və yeni nodun sol və sağ qiymətləri üçün DFS çağırırıq.
  5. dəyər “#” olarsa, biz NULL qaytarırıq.

İkili Ağacın Serializasiyası və Seriyadan çıxarılması üçün kod

C ++ Proqramı

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
private:
    void _serialize(TreeNode* root, string& s) {
        if(!root) {
            s += "# ";
            return;
        }
        s += (to_string(root->val) + " ");
        _serialize(root->left, s);
        _serialize(root->right, s);
    }
    
    TreeNode* _deserialize(istringstream& ss) {
        string value;
        ss >> value;
        if(value == "#") return NULL;
        TreeNode* node = new TreeNode(stoi(value));
        node->left = _deserialize(ss);
        node->right = _deserialize(ss);        
        return node;
    }
public:
    string serialize(TreeNode* root) {
        string data = "";
        _serialize(root, data);
        return data;
    }

    TreeNode* deserialize(string data) {
        istringstream ss(data);
        return _deserialize(ss);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

Java Proqramı

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    StringBuilder sb = new StringBuilder();
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        preorderTraversal(root);
        return sb.toString();
    }
    void preorderTraversal(TreeNode root){
        if(root==null){
            sb.append("n ");
            return;
        }
        sb.append(root.val+" ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }
    // Decodes your encoded data to tree.
    int index = 0;
    public TreeNode deserialize(String data) {
        String[] ss = data.split(" ");
        return prebuild(ss);
    }
    TreeNode prebuild(String[] ss){
        if(index>=ss.length)return null;
        if(ss[index].equals("n"))return null;
        TreeNode node = new TreeNode(Integer.parseInt(ss[index]));
        index++;
        node.left=prebuild(ss);
        index++;
        node.right=prebuild(ss);
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

İkili Ağacın Serializasiyası və Seriyadan Çıxarılması üçü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)

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