ഒരു ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിൽ തിരയുക  


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആപ്പിൾ ഐബിഎം
അൽഗോരിതം ബൈനറി തിരയൽ മരം കോഡിംഗ് അഭിമുഖം അഭിമുഖം ലീട്ട് കോഡ് LeetCodeSolutions

ഈ പ്രശ്‌നത്തിൽ, ഞങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് ബൈനറി തിരയൽ മരം ഒരു പൂർണ്ണസംഖ്യ. തന്നിരിക്കുന്ന സംഖ്യയ്ക്ക് തുല്യമായ മൂല്യമുള്ള ഒരു നോഡിന്റെ വിലാസം ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്. ഒരു ചെക്ക് എന്ന നിലയിൽ, ഈ നോഡ് റൂട്ടായി ഉള്ള സബ് ട്രീയുടെ പ്രീഓർഡർ ട്രാവെർസൽ ഞങ്ങൾ പ്രിന്റുചെയ്യേണ്ടതുണ്ട്. ട്രീയിൽ നൽകിയിരിക്കുന്ന സംഖ്യയ്ക്ക് തുല്യമായ മൂല്യമില്ലെങ്കിൽ, ഞങ്ങൾ മടങ്ങേണ്ടതുണ്ട് NULL, അതായത്, ഒഴിഞ്ഞ വൃക്ഷം.

ഉദാഹരണം  

     2
    
  /     \

1         3

             \

               4


Target Value = 3
3 4
     5

  /      \

1         10 


Target Value = 4
Empty BST

വിശദീകരണം # 1

ബിഎസ്ടി 3 മൂല്യമുള്ള ഒരു നോഡ് ഉൾക്കൊള്ളുന്നു, അതിനാൽ ഞങ്ങൾ അതിന്റെ ഉപവീക്ഷണം മടക്കി അതിന്റെ പ്രീഓർഡർ ട്രാവെർസൽ പ്രിന്റുചെയ്യുന്നു.

വിശദീകരണം # 2

ബിഎസ്ടി 4 മൂല്യമുള്ള ഒരു നോഡും അടങ്ങിയിട്ടില്ല, അതിനാൽ ഞങ്ങൾ എൻ‌യു‌എൽ‌എൽ മടക്കി “ശൂന്യമായ ജിഎസ്ടി” അച്ചടിക്കുന്നു.

സമീപനം (ആവർത്തന)  

ഈ കേസിൽ ഉപപ്രശ്നത്തെ ഒരു പ്രശ്നം എങ്ങനെ ആശ്രയിച്ചിരിക്കുന്നുവെന്ന് നമുക്ക് ചിന്തിക്കാം. ഞങ്ങളുടെ ഫംഗ്ഷൻ കണ്ടെത്തിയാൽ ടാർഗെറ്റ് മൂല്യമുള്ള നോഡിന്റെ വിലാസം നൽകുന്നു. വൃക്ഷത്തിന്റെ വേരിൽ നിന്നാണ് ഞങ്ങൾ ആരംഭിക്കുന്നത്. ഈ നോഡ് ആണെങ്കിൽ ശൂന്യം, ഞങ്ങൾ‌ ബൈനറി തിരയൽ‌ ട്രീയുടെ അവസാനത്തിലെത്തിയെന്നത് വ്യക്തമാണ്, അതിനാൽ‌ ടാർ‌ഗെറ്റ് മൂല്യമുള്ള നോഡ് ഇല്ല. അതിനാൽ, ഞങ്ങൾ മടങ്ങുന്നു ശൂന്യം. അതുപോലെ, ഞങ്ങൾ നോഡ് മൂല്യം ടാർഗെറ്റ് മൂല്യത്തിന് തുല്യമാണ്, ഞങ്ങൾ ഈ നോഡ് നൽകുന്നു. അല്ലെങ്കിൽ, ടാർഗെറ്റ് മൂല്യമുള്ള നോഡ് ഒന്നുകിൽ ഉണ്ടായിരിക്കുമെന്ന് ഞങ്ങൾക്കറിയാം ഇടത്തെ സബ്‌ട്രീ അല്ലെങ്കിൽ വലത് നിലവിലെ റൂട്ടിന്റെ സബ്‌ട്രീ. റൂട്ട് മൂല്യവും ടാർഗെറ്റ് മൂല്യവും താരതമ്യപ്പെടുത്തി നമുക്ക് ദിശ (ഇടത്തോട്ടോ വലത്തോട്ടോ) തീരുമാനിക്കാം. അതിനാൽ, ഞങ്ങൾ അതേ ആവർത്തന ഫംഗ്ഷനെ വിളിക്കുന്നു വേര് as root.left or root.right.

ഒരു ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിൽ തിരയുകമൊട്ടുസൂചി

അൽഗോരിതം

  1. ഒരു ഫംഗ്ഷൻ സൃഷ്ടിക്കുക searchBST () ടാർ‌ഗെറ്റ് വിലാസം നൽ‌കുന്നതിന്
  2. If വേര് തുല്യമാണ് ശൂന്യം OR വേര് ടാർഗറ്റിന്റെ അതേ മൂല്യമുണ്ട്:
    • റിട്ടേൺ റൂട്ട്
  3. ടാർഗെറ്റ് മൂല്യത്തേക്കാൾ root.value വലുതാണെങ്കിൽ:
    1. മടക്കം searchBST (root.left, val)
  4. മടങ്ങുക searchBST (root.right, val)
  5. ടാർഗെറ്റ് നോഡിന്റെ പ്രീഓർഡർ ട്രാവെർസൽ പ്രിന്റുചെയ്യുക
ഇതും കാണുക
ബൈനറി ട്രീ ഡാറ്റ ഘടന

ഒരു ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിൽ തിരയൽ നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം

#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

ഒരു ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലെ തിരയലിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (H), H = logN = ശരാശരി കേസുകളിൽ ജിഎസ്ടിയുടെ ഉയരം കൂടാതെ O (N), N. = മോശം സാഹചര്യങ്ങളിൽ ജിഎസ്ടിയുടെ വലുപ്പം. ജി‌എസ്‌ടി വളച്ചൊടിക്കുമ്പോൾ സംഭവിക്കുന്ന ഏറ്റവും മോശം അവസ്ഥയിൽ ഒരിക്കൽ ഞങ്ങൾ മരം കടക്കുന്നു.

സ്ഥല സങ്കീർണ്ണത

O (H) ഓരോ നോഡിലും സഞ്ചരിക്കാൻ ഞങ്ങൾ ആവർത്തന കോളുകൾ ഉപയോഗിക്കുമ്പോൾ ശരാശരി സന്ദർഭങ്ങളിൽ. O (N) ഏറ്റവും മോശം അവസ്ഥയിൽ. ചില കംപൈലറുകൾ പ്രവർത്തനക്ഷമമാക്കുന്നു എന്നതാണ് ഒരു പ്രധാന കുറിപ്പ് വാൽ-ആവർത്തനം അത്തരം സന്ദർഭങ്ങളിൽ, സ്ഥല സങ്കീർണ്ണത മാറുന്നു O (1).

ഇതും കാണുക
ഒരു പർവതനിരയിലെ കൊടുമുടി സൂചിക

സമീപനം (ആവർത്തനം)  

മുകളിലുള്ള സമീപനത്തിന് സമാനമായി, ടാർ‌ഗെറ്റ് മൂല്യം നിലവിലെ നോഡിൽ‌ ഇല്ലെങ്കിൽ‌, നമുക്ക് ഇടത്തോട്ടോ വലത്തോട്ടോ സബ്‌ട്രീയിലേക്ക് പോകാം, അസൈൻ‌ ചെയ്‌തുകൊണ്ട് നമുക്ക് ഇത് ആവർത്തനപരമായി ചെയ്യാൻ‌ കഴിയും റൂട്ട് = root.left or റൂട്ട് = root.right റൂട്ട് ആകുന്നതുവരെ എല്ലാ ആവർത്തനത്തിലും ശൂന്യം. ഏതെങ്കിലും ആവർത്തന സമയത്ത് റൂട്ടിന്റെ മൂല്യം ടാർഗെറ്റ് മൂല്യത്തിന് തുല്യമാണെന്ന് ഞങ്ങൾ കണ്ടെത്തിയാൽ, ഞങ്ങൾ ആ റൂട്ട് നൽകുന്നു. അല്ലെങ്കിൽ, ഞങ്ങൾ മടങ്ങുന്നു ശൂന്യം.

അൽഗോരിതം

  1. സമാനമായ ഒരു പ്രവർത്തനം സൃഷ്ടിക്കുക searchBST () അത് ടാർഗെറ്റ് നോഡിന്റെ വിലാസം നൽകുന്നു
  2. അതേസമയം വേര് is അല്ല ശൂന്യം:
    • if റൂട്ട്. മൂല്യം ടാർഗെറ്റ് മൂല്യത്തിന് തുല്യമാണ്
      • മടക്കം വേര്
    • if root.val is കൂടുതൽ ടാർഗെറ്റ് മൂല്യത്തേക്കാൾ
      • വലത് സബ്‌ട്രീയിലേക്ക് ഇതായി നീക്കുക: റൂട്ട് = root.right
    • മറ്റാരെങ്കിലും
      • ഇടത് സബ്‌ട്രീയിലേക്ക് ഇതായി നീക്കുക: റൂട്ട് = root.left
  3. മടങ്ങുക ശൂന്യം
  4. ടാർഗെറ്റ് നോഡിന്റെ പ്രീഓർഡർ ട്രാവെർസൽ പ്രിന്റുചെയ്യുക

ഒരു ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിൽ തിരയൽ നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം

#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

ഒരു ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലെ തിരയലിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (H = logN) ശരാശരി കേസുകളിലും O (N) മേൽപ്പറഞ്ഞ സമീപനത്തിന് സമാനമായ മോശം സാഹചര്യങ്ങളിൽ (വളച്ചൊടിച്ച ജിഎസ്ടി).

ഇതും കാണുക
ലെവൽ ഓർഡർ സർപ്പിള രൂപത്തിൽ സഞ്ചരിക്കുന്നു

സ്ഥല സങ്കീർണ്ണത

O (1) ഞങ്ങൾ സ്ഥിരമായ മെമ്മറി ഇടം മാത്രം ഉപയോഗിക്കുന്നതിനാൽ.