İkili Axtarış Ağacı Leetcode həllinə daxil edin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Atlassian Facebook google microsoft
alqoritmlər İkili Axtarış Ağacı kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 28

Bu problemdə bizə a-nın kök düyünü verilir İkili Axtarış Ağacı ikili axtarış ağacına əlavə etməli və quruluşunu qaytarmalı olduğumuz bir bütöv dəyər və bir qovşağın bir tam dəyərini ehtiva edir. Elementi BST-yə əlavə etdikdən sonra, onun içərisindən keçidini çap etməliyik.

misal

Binary Search Tree:
 
    7
 
  /     \

3         10

        /

      8
Integer Value = 11
3 7 8 10 11
Binary Search Tree:
           5

         /

       4

     /

   3
Integer Value = 2
2 3 4 5

Izahat

İkili Axtarış Ağacı Leetcode həllinə daxil edinPin

İkili Axtarış Ağacı Leetcode həllinə daxil edinPin

Yanaşma (Rekursiv)

İkili Axtarış Ağacımızda hər hansı bir qovşağın harada yerləşdiriləcəyinə qərar vermək üçün kökündən sol / sağ uşağı verilən qovşaq olacaq müvafiq qovşağa bir yol qurmalıyıq.

Tapşırığı problemdən alt probleminə ötürərək bunu təkrarən həll edə bilərik. Bu vəziyyətdə bir ağaca yeni bir qovşaq qoymaq onu sol alt ağacına və ya sağ alt ağacına əlavə etmək deməkdir. Eyni fikir digər subtrees üçün də mövcuddur. Bir baza işi qurmalıyıq. Hər hansı bir alt ağacın kök düyünün olduğu bir nöqtəyə çatdıqda NULL, hədəf nodu daxil etmək üçün yolun sonuna çatdığımız deməkdir. Beləliklə, a yeni verilmiş dəyər kimi düyün dəyəri olan qovşaq ünvanı. İkili Axtarış Ağacları, içəridəki hər hansı bir elementi axtarmaq üçün əhəmiyyətli bir üstünlükə malikdir O (logN) orta hallarda aşağı vaxt. Beləliklə, bu vəziyyətdə, səmərəli vaxt daxil ediləcək yeni düyünün yerini tapırıq.

Alqoritm

  1. Bir funksiya yaradın insertIntoBST () ünvanını qaytaran kök verildikdən sonra BST-nin node
  2. insertIntoBST () iki parametr var: kök ağacın və dəyər yerləşdiriləcək düyünün
  3. Funksiya aşağıdakıları edəcək:
    • If kök is SIFIR, verilmiş dəyərlə eyni dəyəri olan yeni bir ağac nodu qaytarın
    • Verilən dəyər böyük dəyərindən daha çox kök node, sonra eyni problemi sağ alt ağaca çağırın və sonra kökü qaytarın
      • kök. hüququ = insertIntoBST (kök-> sağ, dəyər)
      • qayıtmaq kök
    • Sol alt ağacdakı başqa axtarış:
      • kök. sol= insertIntoBST (kök. sol, dəyər)
      • qayıtmaq kök
  4. İkili Axtarış Ağacının inorder keçidini çap edin

Binary Search Tree Leetcode həllinə əlavə edin

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
    return;
}


BSTNode* insertIntoBST(BSTNode* root , int val)
{
    if(root == NULL)
        return new BSTNode(val);
    if(val > root->value)
    {
        root->right = insertIntoBST(root->right , val);
        return root;
    }
    root->left = insertIntoBST(root->left , val);
    return root;
}

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

Java Proqramı

class BSTNode
{
    int value;
    BSTNode left , right;

    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        if(val > root.value)
        {
            root.right = insertIntoBST(root.right , val);
            return root;
        }
        root.left = insertIntoBST(root.left , val);
        return root;
    }

    static void inorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.value + " ");
        inorderTraversal(root.right);
        return;
    }
}

3 7 8 10 11

Binary Search Tree Leetcode həllinə əlavəin mürəkkəbliyi təhlili

Zamanın mürəkkəbliyi

O (H) = BST hündürlüyü = giriş (burada N = BST-də qovşaq sayı) orta hallarda (logN rekursiv zənglər etdiyimiz kimi). Amma O (N) ən pis halda ağac əyilmiş bir ağac olduqda. Çünki ağacın əyri olması halında axtarış a olur xətti bir.

Kosmik mürəkkəblik

O (H) orta hallarda. O (N) ən pis halda. Məkan Mürəkkəbliyi ilə iş, zamanın mürəkkəbliyi ilə eynidir, çünki etdiyimiz rekursiv zənglərin sayından asılıdır.

Yanaşma (Iterative)

Kosmik mürəkkəbliyi yaxşılaşdırmaq üçün yuxarıdakı yanaşmanı təkrarən izləyə bilərik. Rekursiya, yaddaş yeyən yığma çərçivələrdən istifadə edir. Beləliklə, təkrarlanan həll yolunda qarşısını alırıq rekursiv zəng yükü və soldan və ya sağdan biri olan bir düyünü vurana qədər axtarış yolumuzdakı ağacdan en NULL. Nə zaman var root.left / root.right = NULL, bu düyünü verilən dəyərlə eyni dəyəri olan yeni bir düyünə bərabər qoyduq. Diqqəti müqayisə edərək yolu seçdiyimizi unutmayın kök hər rekursiya çağırışında dəyər.

Alqoritm

  1. Yenidən var insertIntoBST () yuxarıdakı kimi eyni məqsədlə
  2. Əgər kök boşdur
    1. verilmiş dəyərlə eyni dəyəri olan yeni nodu qaytarın
  3. Kökün bir nüsxəsini yaradın dummy BST məzmunu ilə manipulyasiya etmək
  4. Isə dummy is yox NULL
    1. verilən dəyər böyükdürsə kök.val
      1. If kök. hüququ boşdur
        1. kök. hüququ = verilmiş dəyəri olan yeni qovşaq
        2. qayıtmaq kök
      2. Başqa bir şey
        1. kök = kök. hüququ, sağ alt ağaca tullanmaq
    2. Dəyər az və ya bərabər olduqda başqa bir şeydir kök.val
      1. Root.left NULL olduqda
        1. kök. sol = verilmiş dəyəri olan yeni qovşaq
        2. qayıtmaq kök
      2. Başqa bir şey
        1. kök = kök. sol, sol subtree keçmək
  5. BST-nin Inorder keçidini çap edin

Binary Search Tree Leetcode həllinə əlavə edin

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
    return;
}

BSTNode* insertIntoBST(BSTNode* root , int val)
{
    if(root == NULL)
        return new BSTNode(val);
    BSTNode* dummy = root;
    while(dummy != NULL)
    {
        if(val > dummy->value)
        {
            if(dummy->right == NULL)
            {
                dummy->right = new BSTNode(val);
                return root;
            }
            else
                dummy = dummy->right;
        }
        else
        {
            if(dummy->left == NULL)
            {
                dummy->left = new BSTNode(val);
                return root;
            }
            else
                dummy = dummy->left;
        }
    }
    return root;
}

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

Java Proqramı

class BSTNode
{
    int value;
    BSTNode left , right;

    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        BSTNode dummy = root;
        while(dummy != null)
        {
            if(val > dummy.value)
            {
                if(dummy.right == null)
                {
                    dummy.right = new BSTNode(val);
                    return root;
                }
                else
                    dummy = dummy.right;
            }
            else
            {
                if(dummy.left == null)
                {
                    dummy.left = new BSTNode(val);
                    return root;
                }
                else
                    dummy = dummy.left;
            }
        }
        return root;
    }

    static void inorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.value + " ");
        inorderTraversal(root.right);
        return;
    }
}

3 7 8 10 11

Binary Search Tree Leetcode həllinə əlavəin mürəkkəbliyi təhlili

Zamanın mürəkkəbliyi

O (H) = BST hündürlüyü = giriş (burada N = BST-də qovşaq sayı) orta hallarda. Amma O (N) ən pis halda ağac əyilmiş bir ağac olduqda. Yenə də zamanın mürəkkəbliyi, təyin olunan yerə çatmaq üçün etdiyimiz təkrar sayından asılıdır və bundan sonra verilmiş düyünün yerləşdirilməsi lazımdır və bu ağac sətirindən asılıdır.

Kosmik mürəkkəblik

O (1). Ən pis vəziyyətdə də, dəyişənlər üçün yalnız daimi yerdən istifadə edirik.

Şərh yaz

Translate »
1