Որոնեք Երկուական որոնման ծառի Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են խնձոր IBM
Երկուական որոնման ծառ

Այս խնդրում մեզ տրվում է ա Երկուական որոնման ծառ և ամբողջ թիվ: Մենք պետք է գտնենք հանգույցի հասցեն, որի արժեքը նույնն է, ինչ տրված ամբողջ թիվն է: Որպես ստուգում, մենք պետք է տպենք ենթա-ծառի նախնական պատվերի անցումը, որն այս հանգույցն ունի որպես արմատ: Եթե ​​ծառի մեջ տրված ամբողջ թվին հավասար արժեք չկա, մենք պետք է վերադառնանք 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»:

Մոտեցում (ռեկուրսիվ)

Եկեք մտածենք, թե ինչպես է խնդիրը կախված այս պարագայում ենթախնդրից: Ասենք, որ մեր ֆունկցիան գտնում է, եթե գտնում է, հանգույցի հասցեն հասցեական արժեքով է վերադարձնում: Մենք սկսում ենք ծառի արմատից: Եթե ​​այս հանգույցն է Նուլ ակնհայտ է, որ մենք հասել ենք երկուական որոնման ծառի ավարտին, ուստի նպատակային արժեքով հանգույց գոյություն չունի: Այսպիսով, մենք վերադառնում ենք ԴԱՏԱՐԿ. Նմանապես, մենք հանգույցի արժեքը հավասար է նպատակային արժեքին, մենք վերադարձնում ենք այս հանգույցը: Հակառակ դեպքում, մենք գիտենք, որ նպատակային արժեք ունեցող հանգույցը կա՛մ կլինի դուրս ենթատեսակ կամ իրավունք ընթացիկ արմատի ենթածառը: Մենք կարող ենք որոշել ուղղությունը (ձախ կամ աջ) ՝ համեմատելով root.value և նպատակային արժեքը: Այսպիսով, մենք անվանում ենք նույն ռեկուրսիվ գործառույթը հետ արմատ as արմատ. ձախ or արմատ. իրավունք

Որոնեք Երկուական որոնման ծառի Leetcode լուծում

Ալգորիթմ

  1. Ստեղծել գործառույթ searchBST () նպատակային հասցեն վերադարձնելու համար
  2. If արմատ հավասար է զրո OR արմատ ունի նույն արժեքը, ինչ թիրախը.
    • Վերադարձ արմատ
  3. Եթե ​​root.value- ն ավելի մեծ է, քան թիրախային արժեքը.
    1. վերադարձնել searchBST (root.left, val)
  4. Վերադառնալ searchBST (արմատ. աջ, վալ)
  5. Տպեք նպատակային հանգույցի նախնական պատվերի անցումը

Երկուական որոնման ծառի Leetcode լուծման մեջ որոնման իրականացում

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;
}

Java ծրագիր

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 լուծման մեջ որոնման բարդության վերլուծություն

Timeամանակի բարդություն

O (H), H = logN = BST- ի բարձրությունը միջին դեպքերում և Օ (Ն), Ն = BST- ի չափը վատագույն դեպքերում: Մենք ծառը կտրում ենք մեկ անգամ վատագույն դեպքում, որը տեղի է ունենում, երբ BST- ը շեղվում է:

Տիեզերական բարդություն

Ո (Հ) միջին դեպքերում, երբ մենք օգտագործում ենք ռեկուրսիվ զանգեր յուրաքանչյուր հանգույց անցնելու համար: ՎՐԱ) վատագույն դեպքում Կարևոր նշում է, որ որոշ կազմողներ հնարավորություն են տալիս պոչ-ռեկուրսիա և այդ դեպքերում տիեզերական բարդությունը դառնում է Ո (1).

Մոտեցում (կրկնություն)

Վերոնշյալ մոտեցման նման, մենք կարող ենք ցատկել ձախ կամ աջ ենթատեսակ, եթե թիրախային արժեքը ներկա հանգույցում չկա, մենք կարող ենք դա անել կրկնում ՝ նշանակելով արմատ = արմատ: ձախ or արմատ = արմատ: ճիշտ յուրաքանչյուր կրկնության ժամանակ, մինչև արմատը դառնա դատարկ. Եթե ​​գտնենք, որ արմատի արժեքը հավասար է թիրախային արժեքի ցանկացած կրկնության դեպքում, մենք կվերադարձնենք այդ արմատը: Հակառակ դեպքում, մենք վերադառնում ենք դատարկ.

Ալգորիթմ

  1. Ստեղծեք նմանատիպ գործառույթ searchBST () որը վերադարձնում է նպատակային հանգույցի հասցեն
  2. Ժամանակ արմատ is Նշում դատարկ:
    • if արմատ. արժեք հավասար է նպատակային արժեքին
      • վերադարձնել արմատ
    • if արմատ .val is ավելի մեծ քան նպատակային արժեքը
      • Տեղափոխվել աջ ենթածառ, ինչպես. արմատ = արմատ: ճիշտ
    • ուրիշ
      • Տեղափոխեք ձախ ենթածառ ՝ արմատ = արմատ: ձախ
  3. Վերադառնալ զրո
  4. Տպեք նպատակային հանգույցի նախնական պատվերի անցումը

Երկուական որոնման ծառի Leetcode լուծման մեջ որոնման իրականացում

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;
}

Java ծրագիր

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 լուծման մեջ որոնման բարդության վերլուծություն

Timeամանակի բարդություն

O (H = logN) միջին դեպքերում և ՎՐԱ) վատագույն դեպքերում (շեղված BST), նույնը, ինչ վերը նշված մոտեցումն է:

Տիեզերական բարդություն

Ո (1) քանի որ մենք օգտագործում ենք միայն մշտական ​​հիշողության տարածություն: