Binary Search Tree Leetcode Solution တွင်ရှာပါ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Apple IBM က
Binary Search Tree

ဒီပြproblemနာမှာငါတို့ကိုပေးထားတယ် Binary Search Tree နှင့်ကိန်းတစ်ခု။ node တစ်ခု၏တန်ဖိုးကိုပေးထားသောကိန်းနှင့်တူညီသည်။ စစ်ဆေးမှုအနေနှင့်၊ ဤ node သည် root အဖြစ်ရှိသော sub-tree ၏ preorder traversal ကို print ထုတ်ရန်လိုအပ်သည်။ သစ်ပင်၌ပေးထားသောကိန်းနှင့်ထပ်တူတန်ဖိုးမရှိပါကကျွန်ုပ်တို့ပြန်လာရန်လိုသည် nullဆိုလိုသည်မှာအပင်တစ်ပင်မျှမရှိ။

နမူနာ

     2
    
  /     \

1         3

             \

               4


Target Value = 3
3 4
     5

  /      \

1         10 


Target Value = 4
Empty BST

ရှင်းလင်းချက် # 1

BST တွင်တန်ဖိုး 3 ပါသည့် node တစ်ခုပါရှိသည်၊ ထို့ကြောင့်ကျွန်ုပ်တို့သည်၎င်း၏သစ်ပင်ခွဲများကိုပြန်ပို့ပြီးယင်း၏ကြိုတင်မှာယူမှုဖြတ်သန်းမှုကို print ထုတ်သည်။

ရှင်းလင်းချက် # 2

BST တွင်တန်ဖိုး ၄ ပါသော node များမပါ ၀ င်သောကြောင့်ကျွန်ုပ်တို့သည် NULL ကိုပြန်ပို့ပြီး“ Empty BST” ကို print ထုတ်သည်။

ချဉ်းကပ်နည်း (Recursive)

ဤကိစ္စတွင်ပြproနာတစ်ခုသည်ပြsubနာတစ်ခုပေါ်တွင်မူတည်သည်ကိုစဉ်းစားကြည့်ကြစို့။ ဆိုကြပါစို့၊ ကျွန်ုပ်တို့၏ function သည် node လိပ်စာကို target value နှင့် return ပြန်လျှင်ဆိုပါစို့။ သစ်ပင်၏အမြစ်မှကျွန်ုပ်တို့စတင်သည်။ ဒီ node ကိုလျှင် null ကျနော်တို့ binary search tree ရဲ့အဆုံးကိုရောက်ပြီဆိုတာသိသာထင်ရှားပြီး target value နဲ့ node မရှိဘူး။ ဒါကြောင့်ကျနော်တို့ကပြန်လာ null ။ အလားတူစွာကျွန်ုပ်တို့ node တန်ဖိုးသည် target တန်ဖိုးနှင့်ညီသည်၊ ကျွန်ုပ်တို့သည်ဤ node ကိုပြန်ပို့သည်။ ဒီလိုမှမဟုတ်ရင် target-တန်ဖိုး node တစ်ခုခုဖြစ်မယ်ဆိုတာငါတို့သိတယ် လက်ဝဲဘက် ဇော်ဂျီ မှန်သော လက်ရှိအမြစ်၏ subtree ။ root.value နှင့် target value တို့ကိုနှိုင်းယှဉ်ခြင်းအားဖြင့်ကျွန်ုပ်တို့သည်လမ်းကြောင်း (ဘယ်သို့မဟုတ်ညာ) ဆုံးဖြတ်နိုင်သည်။ ဒါကြောင့်ကျွန်တော်တို့ဟာအတူတူ recursive function ကိုခေါ်ပါ အမြစ် as root.left or root.right ။

Binary Search Tree Leetcode Solution တွင်ရှာပါ

algorithm

  1. function တစ်ခုဖန်တီးပါ searchBST () ပစ်မှတ်လိပ်စာပြန်လာရန်
  2. If အမြစ် ညီမျှသည် တရားမဝင်သော OR အမြစ် ပစ်မှတ်၏တန်ဖိုးကဲ့သို့တူညီသောတန်ဖိုးရှိ:
    • အမြစ်ကိုပြန်သွားပါ
  3. root.value ဟာ target value ထက်ကြီးရင်၊
    1. ပြန်လာ searchBST (root.left, val)
  4. ပြန်လာ searchBST (root.right, val)
  5. ပစ်မှတ် node ကို၏ preorder ဖြတ်သန်းပုံနှိပ်ပါ

ရှာဖွေမှုများကို Binary Search Tree 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;
}

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

ရှုပ်ထွေးမှုအားရှာဖွေခြင်းအား Binary Search Tree Leetcode Solution တွင်ရှာဖွေခြင်း

အချိန်ရှုပ်ထွေး

အို (H) H ကို = logN = ပျမ်းမျှကိစ္စများတွင် BST ၏အမြင့်နှင့် အို (N)၊ အဆိုးဆုံးကိစ္စများတွင် BST ၏အရွယ်အစား။ ကျနော်တို့ BST skewed အတွက်ဖြစ်ပေါ်သောအဆိုးဆုံးကိစ္စများတွင်တစ်ချိန်ကသစ်ပင်ဖြတ်သန်း။

အာကာသရှုပ်ထွေးမှု

အို (H) ပျမ်းမျှကိစ္စများတွင်ကျွန်ုပ်တို့သည် node တိုင်းကိုဖြတ်သန်းရန် recursive ခေါ်ဆိုမှုများကိုအသုံးပြုသည်။ အို (N) အဆိုးဆုံးကိစ္စမှာ။ အရေးကြီးသောမှတ်စုတစ်ခုမှာ compilers အချို့သည် enable လုပ်ရန်ဖြစ်သည် အမြီး - ပြန်သွား နှင့်ထိုကိစ္စများတွင်အာကာသရှုပ်ထွေးဖြစ်လာသည် အို (၁).

ချဉ်းကပ်မှု (ကြားမှာ)

အထက်ပါချဉ်းကပ်နည်းနှင့်ဆင်တူသည်မှာလက်ရှိ node တွင်ပစ်မှတ်တန်ဖိုးမရှိပါကကျွန်ုပ်တို့သည်လက်ဝဲသို့မဟုတ်ညာသို့ subtree သို့ခုန်နိုင်သည်။ root = root.left or root = root.right အမြစ်ဖြစ်လာသည်အထိတိုင်းကြားမှာ တရားမဝင် အကယ်၍ root တန်ဖိုးသည်မည်သည့်ကြားမှာမဆို target target နှင့်တူညီကြောင်းတွေ့ရှိပါက၎င်း root ကိုကျွန်ုပ်တို့ပြန်ပို့သည်။ ဒီလိုမှမဟုတ်ရင်ကျနော်တို့ပြန်လာ တရားမဝင်

algorithm

  1. အလားတူ function ကိုဖန်တီးပါ searchBST () ကြောင်းပစ်မှတ် node ကို၏လိပ်စာပြန်လည်ရောက်ရှိ
  2. စဉ် အမြစ် is မဟုတ် တရားမဝင်သော
    • if root.value ပစ်မှတ်တန်ဖိုးညီမျှသည်
      • ပြန်လာ အမြစ်
    • if root.val is သာ. ကြီး ပစ်မှတ်တန်ဖိုးကိုထက်
      • လက်ျာ subtree သို့ရွှေ့ပါ - root = root.right
    • အခြားသူ
      • ဘယ်ဘက် subtree သို့ရွှေ့ပါ root = root.left
  3. ပြန်လာ တရားမဝင်သော
  4. ပစ်မှတ် node ကို၏ preorder ဖြတ်သန်းပုံနှိပ်ပါ

ရှာဖွေမှုများကို Binary Search Tree 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;
}

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

ရှုပ်ထွေးမှုအားရှာဖွေခြင်းအား Binary Search Tree Leetcode Solution တွင်ရှာဖွေခြင်း

အချိန်ရှုပ်ထွေး

အို (H = logN) ပျမ်းမျှကိစ္စများတွင်နှင့် အို (N) အဆိုးဝါးဆုံးကိစ္စများတွင် (BST ကိုလွဲချော်သွားသည်)၊ အထက်ပါချဉ်းကပ်နည်းနှင့်အတူတူဖြစ်သည်

အာကာသရှုပ်ထွေးမှု

အို (၁) သာစဉ်ဆက်မပြတ်မှတ်ဉာဏ်အာကာသကိုသုံးပါအဖြစ်။