Çeşidlənmiş Massivi Binar Axtarış Ağacına çevirin LeetCode Həlləri

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Facebook google microsoft Kahin VMware YahooBaxılıb 60

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

Çeşidlənmiş Massivi Binar Axtarış Ağacına çevirin LeetCode Solutions deyir ki, tam ədəd massivi verilir nömrə elementlərin çeşidləndiyi yer artan sifariş, çevirmək bu a hündürlük balanslı ikili axtarış ağacı.

hündürlük balanslı ikili ağac, hər bir qovşağın iki alt ağacının dərinliyi heç vaxt birdən çox fərqlənməyən ikili ağacdır.

Çeşidlənmiş Massivi Binar Axtarış Ağacına çevirin LeetCode HəlləriPin

Misal:

Test işi 1:

Input:

ədədlər = [2, 3, 4, 5, 6, 7, 8, 9]

Çıxış:

[4, 2, 8, null, 3, 6, 9, null, null, 5, 7]

Explanation:

test işi üçün massivi aşağıda göstərildiyi kimi ağaca çevirə bilərik. Şəkildən göründüyü kimi, dərinliyi arasındakı maksimum fərq hər qovşağın 2 alt ağacı 1-dir.

Çeşidlənmiş Massivi Binar Axtarış Ağacına çevirin LeetCode HəlləriPin

Yanaşma

Idea:

Müxtəlif düşünə bilərik ağac traversal texnika və onların xassələri. Biz bilirik InOrder keçidi İkili Axtarış Ağacının nömrəsini verir sıralanmış sıra. Beləliklə, verilən giriş əsasən InOrder keçidi Bu İkili Axtarış Ağacı yaratmalıyıq. Burada problemi həll etməyin əsas açarı etməkdir TreeNode orta nömrədən çıxarın və üzərinə keçin massivin sol yarısı bir forma Sol ağac massivin sağ yarısı bir forma sağ ağac.

Kodu

Sıralanmış Massivi Binar Axtarış Ağacına çevirmək üçün Java Proqramı

class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
      if (num.length == 0) {
          return null;
      }
      TreeNode root = arrayToTreeConverter(num, 0, num.length - 1);
      return root;
    }

    public TreeNode arrayToTreeConverter(int[] num, int low, int high) {
        if (low > high) { 
            return null;
        }
        int mid = (low + high) / 2;
        TreeNode root = new TreeNode(num[mid]);
        root.left = arrayToTreeConverter(num, low, mid - 1);
        root.right = arrayToTreeConverter(num, mid + 1, high);
        return root;
    }
}

Sıralanmış Massivi Binar Axtarış Ağacına çevirmək üçün C++ proqramı

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
      if (nums.size() == 0) {
          return NULL;
      }
      TreeNode* root = arrayToTreeConverter(nums, 0, nums.size() - 1);
      return root;
    }
    TreeNode* arrayToTreeConverter(vector<int>& nums, int low, int high) {
      if (low > high) { 
        return NULL;
      }
      int mid = (low + high) / 2;
      TreeNode* root = new TreeNode(nums[mid]);
      root->left = arrayToTreeConverter(nums, low, mid - 1);
      root->right = arrayToTreeConverter(nums, mid + 1, high);
      return root;
    }
};

Çeşidlənmiş Massivi Binar Axtarış Ağacına çevirmək üçün mürəkkəblik təhlili LeetCode Həll

Zamanın mürəkkəbliyi

Burada hər qovşağı tam olaraq bir dəfə keçirik. Beləliklə, zamanın mürəkkəbliyi O (n). (n ağacdakı qovşaqların sayıdır)

Kosmik Mürəkkəblik

Burada kosmik mürəkkəblik əslində rekursiya balanslaşdırılmış ağac üçün olmalıdır yığını O (logn). Beləliklə, kosmik mürəkkəblik O(logn).

Referans: https://en.wikipedia.org/?title=Inorder_traversal&redirect=yes

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