BST Leetcode ဖြေရှင်းချက်အတွက်အနည်းဆုံးအကြွင်းမဲ့ကွာခြားချက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Google
သစ်ပင်

ပြSTနာ BST Leetcode Solution တွင်အနည်းဆုံးအကြွင်းမဲ့ကွဲပြားခြားနားမှုကသင်နှင့်အတူရှိသည်ဟုဖော်ပြသည် Binary Search Tree။ တဖန်သင်တို့ BST တစ်ခုလုံးအတွက်နိမ့်ဆုံးအကြွင်းမဲ့အာဏာခြားနားချက်ကိုရှာဖွေရန်လိုအပ်သည်။ BST သို့မဟုတ် Binary Search Tree ဆိုသည်မှာစည်းမျဉ်းကိုလိုက်နာသောအချို့သော node များပါသောသစ်ပင်မှအပအခြားဖြစ်သည်။ စည်းမျဉ်းတစ်ခု node တစ်ခု၏ဘယ်ဘက် subtree သည်လက်ရှိ node ထက်တန်ဖိုးနိမ့်သော node များသာပါဝင်ရမည်ဖြစ်သည်။ အလားတူစွာမှန်ကန်သော subtree အတွက် node များသည်လက်ရှိ node ထက်သာလွန်သောတန်ဖိုးများရှိရမည်။ ထို့ကြောင့်ပုံမှန်အားဖြင့်ကျွန်ုပ်တို့သည်ဖြေရှင်းနည်းသို့မကူးမီဥပမာအချို့ကိုအရင်ကြည့်ရှုရမည်။

BST Leetcode ဖြေရှင်းချက်အတွက်အနည်းဆုံးအကြွင်းမဲ့ကွာခြားချက်

1

ရှင်းလင်းချက် - node များအကြားခြားနားချက် [1, 2], [2, 3], [3, 4], [4, 5] အားလုံးတွင် 1 ၏ခြားနားချက်ရှိသည်။ ထို့ကြောင့်အဖြေ 1 ဖြစ်ပါတယ်။

BST Leetcode ဖြေရှင်းနည်းတွင်အနည်းဆုံးလုံး ၀ ခြားနားမှုအတွက် Brute Force ချဉ်းကပ်မှု

ပြSTနာက BST Leetcode Solution မှာအနည်းဆုံး Absolute ကွာခြားချက်က Binary Search Tree ရှိ node နှစ်ခုအနက်အနိမ့်ဆုံးခြားနားချက်ကိုရှာဖို့ပြောတယ်။ ထို့ကြောင့်အဖြေကိုရှာရန်နည်းလမ်းမှာ BST ၏မည်သည့်ဒေါင်လိုက် (သို့) node မဆို ရွေးချယ်၍ ခြားနားချက်ကိုတွက်ချက်ခြင်းဖြစ်သည်။ ယခင်စုံတွဲနှင့်နှိုင်းစာလျှင်အကြွင်းမဲ့ကွာခြားမှုနည်းသောအတွဲတစ်ခုကိုတွေ့ရှိသည်နှင့်ကျွန်ုပ်တို့သည်အဖြေကိုအသစ်ပြောင်းမည်။ အစပိုင်းမှာတော့ node နှစ်ခုကိုသုံးပြီးလုပ်ငန်းစဉ်ရဲ့အဆုံးမှာ။ အဖြေကိုသက်ဆိုင်ရာ variable များတွင်သိမ်းလိမ့်မည်။ ဒီတော့ဒီဖြစ်စဉ်ကိုတူအောင်လုပ်ဖို့ BST ကို inorder ပုံစံနဲ့ဖြတ်ပြီး vector ထဲမှာသိမ်းထားလိမ့်မယ်။ nested loops နှစ်ခုကိုအသုံးပြုပြီးသစ်ပင်ရှိ vertices နှစ်ခုအကြားလုံး ၀ ခြားနားချက်ကိုဆက်ပြီးတွက်ချက်လိမ့်မယ်။

Brute Force ကုဒ်

BST Leetcode Solution အတွက်အနည်းဆုံးလုံး ၀ ခြားနားမှုအတွက် C ++ code

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

struct TreeNode{
    int val;
    TreeNode *left, *right;
};

vector<int> inorder_traversal;
int ans = INT_MAX;

void inorder(TreeNode* root){
    if(root){
        inorder(root->left);
        inorder_traversal.push_back(root->val);
        inorder(root->right);
    }
}

int getMinimumDifference(TreeNode* root) {
    inorder(root);
    for(int i=1;i<inorder_traversal.size();i++)
        ans = min(ans, inorder_traversal[i]-inorder_traversal[i-1]);
    return ans;
}

int main(){
    TreeNode* root = new TreeNode();
    root->val = 1;
    root->right = new TreeNode();
    root->right->val = 5;
    root->right->left = new TreeNode();
    root->right->left->val = 3;
    root->right->left->left = new TreeNode();
    root->right->left->left->val = 2;
    root->right->left->right = new TreeNode();
    root->right->left->right->val = 4;
    cout<<getMinimumDifference(root);
}
1

BST Leetcode Solution အတွက်အနည်းဆုံးလုံး ၀ ခြားနားမှုအတွက် Java ကုဒ်

import java.util.*;
import java.lang.*;
import java.io.*;

class TreeNode{
  int val;
  TreeNode left;
  TreeNode right;
}

class Main {
    static ArrayList<Integer> inorder_traversal = new ArrayList<Integer>();
    static int ans = Integer.MAX_VALUE;
    
    public static void inorder(TreeNode root){
        if(root != null){
            inorder(root.left);
            inorder_traversal.add(root.val);
            inorder(root.right);
        }
    }
    
    public static int getMinimumDifference(TreeNode root) {
        inorder(root);
        for(int i=1;i<inorder_traversal.size();i++)
        	ans = Math.min(ans, inorder_traversal.get(i)-inorder_traversal.get(i-1));
        return ans;
    }
    
    public static void main (String[] args) throws java.lang.Exception
  {
    TreeNode root = new TreeNode();
      root.val = 1;
      root.right = new TreeNode();
      root.right.val = 5;
      root.right.left = new TreeNode();
      root.right.left.val = 3;
      root.right.left.left = new TreeNode();
      root.right.left.left.val = 2;
      root.right.left.right = new TreeNode();
      root.right.left.right.val = 4;
      System.out.print(getMinimumDifference(root));
  }
}
1

ရှုပ်ထွေးဆန်းစစ်ခြင်း

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

အို (N ^ 2) ကျနော်တို့အနိမ့်ဆုံးအကြွင်းမဲ့အာဏာခြားနားချက်ကိုရှာဖွေ 2 အသိုက်ကွင်းကိုအသုံးပြုကတည်းကဒီချဉ်းကပ်မှုအတွက်အချိန်ရှုပ်ထွေး polynomial ဖြစ်လာသည်။

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

အို (N)၊ ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာ inorder traversal ကို vector ဒါမှမဟုတ် array ထဲမှာသိမ်းထားရလို့ပါ။ ထို့ကြောင့်အာကာသရှုပ်ထွေး linear ဖြစ်ပါတယ်။

BST Leetcode ဖြေရှင်းနည်းအတွက်အနည်းဆုံးအကြွင်းမဲ့ကွဲပြားခြားနားမှုအတွက်အကောင်းဆုံးချဉ်းကပ်မှု

inorder ဖြတ်သန်းအသုံးပြုသော BST Leetcode Solution တွင်ပြproblemနာအတွက်အနည်းဆုံးလုံး ၀ ခြားနားချက်အတွက်အထက်ပါချဉ်းကပ်မှု။ ၎င်းသည် inorder traversal ကိုအသုံးပြုသည်သာမက၎င်းသည်သိမ်းဆည်းခြင်းအားဖြင့်အာကာသရှုပ်ထွေးမှုအတွက်ချဉ်းကပ်မှု O (N) ကိုဖြစ်ပေါ်စေသည်။ ငါတို့မှာလည်း BST ရှိတယ်ဆိုတာကိုမသုံးခဲ့ဘူး၊ နိမ့်ဆုံးအကြွင်းမဲ့ခြားနားချက်ကိုဆက်တိုက်ဒေါင်လိုက်နှစ်ခုအကြားသာရရှိနိုင်တယ်။ ဘာလို့လဲဆိုတော့တကယ်တော့ထည့်သွင်းစဉ်းစားမထားဘူး, ငါတို့ polynomial အချိန်ရှုပ်ထွေးရှိခဲ့ပါတယ်။

အကောင်းဆုံးချဉ်းကပ်မှုတွင်ကျွန်ုပ်တို့သည်ယခင် node ကိုလက်ရှိ vertex သို့ခြေရာခံသည်။ ဤသို့ပြုလုပ်ခြင်းသည်အကဲဖြတ်စစ်ဆင်ရေးကို N-1 ကြိမ်သာလုပ်ဆောင်ခြင်းဖြင့်နိမ့်ဆုံးအကြွင်းမဲ့ခြားနားချက်ကိုရှာဖွေရန်ကျွန်ုပ်တို့အားအထောက်အကူပြုသည်။ ၎င်းသည်အမြဲတမ်းနေရာရှုပ်ထွေးမှုရရှိရန်ကျွန်ုပ်တို့အားကူညီပါသည်၊ အကြောင်းမှာကျွန်ုပ်တို့သည် inorder ဖြတ်သန်းမှုတစ်ခုလုံးကိုသိုလှောင်ရန်မလိုဘဲယခင် node ကိုသာသိုလှောင်ရန်မလိုအပ်ပါ။

BST Leetcode ဖြေရှင်းချက်အတွက်အနည်းဆုံးအကြွင်းမဲ့ကွဲပြားခြားနားမှုအတွက်အကောင်းဆုံးကုဒ်နံပါတ်

C ++ ကုဒ်

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

struct TreeNode{
    int val;
    TreeNode *left, *right;
};

TreeNode* previous = NULL;
int ans = INT_MAX;

void inorder(TreeNode* root){
    if(root){
        inorder(root->left);
        if(previous != NULL){
            ans = min(ans, root->val - previous->val);
        }
        previous = root;
        inorder(root->right);
    }
}

int getMinimumDifference(TreeNode* root) {
    inorder(root);
    return ans;
}

int main(){
    TreeNode* root = new TreeNode();
    root->val = 1;
    root->right = new TreeNode();
    root->right->val = 5;
    root->right->left = new TreeNode();
    root->right->left->val = 3;
    root->right->left->left = new TreeNode();
    root->right->left->left->val = 2;
    root->right->left->right = new TreeNode();
    root->right->left->right->val = 4;
    cout<<getMinimumDifference(root);
}
1

ဂျာဗားကုဒ်

import java.util.*;
import java.lang.*;
import java.io.*;

class TreeNode{
  int val;
  TreeNode left;
  TreeNode right;
}

class Main {
    static TreeNode prev = null;
    static int ans = Integer.MAX_VALUE;
    
    public static void inorder(TreeNode root){
        if(root != null){
            inorder(root.left);
            if(prev != null){
                ans = Math.min(ans, root.val - prev.val);
            }
            prev = root;
            inorder(root.right);
        }
    }
    
    public static int getMinimumDifference(TreeNode root) {
        inorder(root);
        return ans;
    }
    
    public static void main (String[] args) throws java.lang.Exception
  {
    TreeNode root = new TreeNode();
      root.val = 1;
      root.right = new TreeNode();
      root.right.val = 5;
      root.right.left = new TreeNode();
      root.right.left.val = 3;
      root.right.left.left = new TreeNode();
      root.right.left.left.val = 2;
      root.right.left.right = new TreeNode();
      root.right.left.right.val = 4;
      System.out.print(getMinimumDifference(root));
  }
}
1

ရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာ

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

အို (N)၊ သစ်ပင်ပေါ်ရှိ N node များကျော် ဖြတ်၍ သွားသောလမ်းကြောင်းကိုသာကျွန်ုပ်တို့အသုံးပြုခဲ့သည်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

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

အို (၁)၊ ကျွန်တော် variable တွေကိုသာစဉ်ဆက်မပြတ်အရေအတွက်ကအသုံးပြုကတည်းက။ အာကာသရှုပ်ထွေးကိုလည်းစဉ်ဆက်မပြတ်အာကာသလျှော့ချ။