მოძებნეთ ორობითი ძიების ხე Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Apple IBM
ორობითი ძებნა ხე

ამ პრობლემის დროს, ჩვენ გვეძლევა ა ორობითი ძებნა ხე და მთელი რიცხვი. ჩვენ უნდა მოვძებნოთ კვანძის მისამართი, რომლის მნიშვნელობაა მოცემული მთელი რიცხვი. შემოწმების სახით, ჩვენ უნდა დავბეჭდოთ ქვე-ხის წინასწარი შეკვეთა, რომელსაც აქვს ეს კვანძი, როგორც root. თუ ხეში მოცემული მთელი რიცხვის იგივე მნიშვნელობა არ არის, უნდა დავბრუნდეთ NULL, ანუ ცარიელი ხე.

მაგალითი

     2
    
  /     \

1         3

             \

               4


Target Value = 3
3 4
     5

  /      \

1         10 


Target Value = 4
Empty BST

განმარტება # 1

BST შეიცავს კვანძს, რომლის მნიშვნელობაა 3, ამიტომ ჩვენ ვუბრუნებთ მის ქვე-ხეს და ვბეჭდავთ მისი წინასწარი შეკვეთის გადაკვეთას.

განმარტება # 2

BST არ შეიცავს არც ერთ კვანძს, რომლის მნიშვნელობაა 4, ასე რომ, ჩვენ ვუბრუნებთ NULL- ს და ვბეჭდავთ "ცარიელი BST".

მიდგომა (რეკურსიული)

მოდით ვიფიქროთ იმაზე, თუ როგორ არის დამოკიდებული პრობლემა ამ შემთხვევაში ქვეპრობლემაზე. ვთქვათ, რომ ჩვენი ფუნქცია დააბრუნებს კვანძის მისამართს სამიზნე მნიშვნელობით, თუ ნაპოვნია. ჩვენ ვიწყებთ ხის ფესვიდან. თუ ეს კვანძია NULL, აშკარაა, რომ ჩვენ მივაღწიეთ ორობითი ძიების ხის დასასრულს და, შესაბამისად, არ არსებობს სამიზნე მნიშვნელობის კვანძი. ასე რომ, ჩვენ ვბრუნდებით NULL. ანალოგიურად, ჩვენ კვანძის მნიშვნელობა უდრის სამიზნე მნიშვნელობას, ამ კვანძს ვუბრუნებთ. წინააღმდეგ შემთხვევაში, ჩვენ ვიცით, რომ სამიზნე შეფასებული კვანძი ან იქნება დარჩა ქვეტყე ან უფლება მიმდინარე ფესვის ქვე ხე. ჩვენ შეგვიძლია განვსაზღვროთ მიმართულება (მარცხნივ ან მარჯვნივ) root.value და სამიზნე მნიშვნელობის შედარებით. ასე რომ, ჩვენ იგივე რეკურსიულ ფუნქციას ვუწოდებთ root as ფესვი.მარცხენა or ფესვი.მართალი.

მოძებნეთ ორობითი ძიების ხე Leetcode Solution

ალგორითმი

  1. ფუნქციის შექმნა searchBST () სამიზნე მისამართის დასაბრუნებლად
  2. If root უდრის null OR root აქვს იგივე მნიშვნელობა, როგორც სამიზნე:
    • დააბრუნე ფესვი
  3. თუ root.value უფრო მეტია ვიდრე სამიზნე მნიშვნელობა:
    1. დაბრუნების searchBST (root.left, val)
  4. დაბრუნების searchBST (root. უფლება, val)
  5. სამიზნე კვანძის წინასწარი შეკვეთის ბეჭდვა

ძიების განხორციელება ორობითი ძიების ხეში Leetcode Solution

C ++ პროგრამა

#include <bits/stdc++.h>
using namespace std;

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int val)
    {
        value = val;
        left = right = NULL;
    }
};

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

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

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

ჯავა პროგრამა

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

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        if(root == null)
            return root;
        if(val == root.value)
            return root;
        if(val < root.value)
            return searchBST(root.left , val);
        return searchBST(root.right , val);
    }

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

ძიების სირთულის ანალიზი ორობითი ძიების ხის Leetcode გადაწყვეტაში

დროის სირთულე

O (H), H = logN = BST– ის სიმაღლე საშუალო შემთხვევებში და O (N), N = BST– ის ზომა უარეს შემთხვევაში. ჩვენ ხეზე გავდივართ ერთხელ ყველაზე ცუდ შემთხვევაში, როდესაც ხდება BST- ის გადახრა.

კოსმოსური სირთულის

O (H) საშუალო შემთხვევებში ვიყენებთ რეკურსიულ ზარებს ყველა კვანძის გადასალახად. O (N) უარეს შემთხვევაში. ერთი მნიშვნელოვანი შენიშვნა არის ის, რომ ზოგიერთი შემდგენელი საშუალებას იძლევა კუდი-რეკურსია და ამ შემთხვევებში ხდება სივრცის სირთულე O (1).

მიდგომა (განმეორებითი)

ზემოაღნიშნული მიდგომის მსგავსად, ჩვენ შეგვიძლია გადახვიდეთ მარცხნივ ან მარჯვნივ ქვეძემდე, თუ სამიზნე მნიშვნელობა არ არის ამჟამინდელ კვანძში, ჩვენ შეგვიძლია გავაკეთოთ ის განმეორებით, მინიჭებით ფესვი = ფესვი. მარცხენა or ფესვი = ფესვი. სწორი ყველა გამეორებაზე, სანამ ფესვი არ გახდება ნულოვანი. თუ აღმოვაჩენთ, რომ ფესვის მნიშვნელობა უდრის სამიზნე მნიშვნელობას ნებისმიერ გამეორებაზე, ჩვენ დავაბრუნებთ ამ ფესვს. წინააღმდეგ შემთხვევაში, ჩვენ ვბრუნდებით ნულოვანი.

ალგორითმი

  1. მსგავსი ფუნქციის შექმნა searchBST () რომელიც აბრუნებს სამიზნე კვანძის მისამართს
  2. მიუხედავად იმისა, root is არ null:
    • if ფესვი. ღირებულება სამიზნე მნიშვნელობის ტოლია
      • დაბრუნების root
    • if root.val is მეტი ვიდრე სამიზნე მნიშვნელობა
      • გადადით მარჯვნივ ქვედა ხეზე, როგორც: ფესვი = ფესვი. სწორი
    • სხვა
      • გადადით მარცხენა ქვევრზე, როგორც: ფესვი = ფესვი. მარცხენა
  3. დაბრუნების null
  4. სამიზნე კვანძის წინასწარი შეკვეთის ბეჭდვა

ძიების განხორციელება ორობითი ძიების ხეში Leetcode Solution

C ++ პროგრამა

#include <bits/stdc++.h>
using namespace std;

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int val)
    {
        value = val;
        left = right = NULL;
    }
};

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

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

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

ჯავა პროგრამა

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

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

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

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

ძიების სირთულის ანალიზი ორობითი ძიების ხის Leetcode გადაწყვეტაში

დროის სირთულე

O (H = logN) საშუალო შემთხვევებში და O (N) უარეს შემთხვევებში (დახრილი BST), ისევე როგორც ზემოთ მოცემული მიდგომა.

კოსმოსური სირთულის

O (1) რადგან ჩვენ ვიყენებთ მხოლოდ მუდმივ მეხსიერების ადგილს.