მინიმალური მანძილი BST კვანძებს შორის Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Google
Recursion ხე

პრობლემა BST კვანძებს შორის მინიმალური მანძილი Leetcode Solution აცხადებს, რომ თქვენ უზრუნველყოფილი ხართ ორობითი ძიების ხე. თქვენ მოეთხოვებათ იპოვოთ მინიმალური განსხვავება მთლიანობაში BST. ასე რომ, თქვენ უნდა იპოვოთ მინიმალური აბსოლუტური სხვაობა BST– ის ნებისმიერ ორ კვანძს შორის. BST ან ორობითი ძიების ხე სხვა არაფერია, თუ არა ხე რამდენიმე კვანძით, რომლებიც იცავს წესს. წესი ისაა, რომ კვანძის მარცხენა ქვეტყე უნდა შეიცავდეს მხოლოდ კვანძებს, რომლებსაც მნიშვნელობა აქვთ მიმდინარე კვანძზე ნაკლები. ანალოგიურად, მარჯვენა ქვეტყისთვის, კვანძები უნდა შეიცავდეს მნიშვნელობებს, ვიდრე მიმდინარე კვანძი. ასე რომ, ჩვეულებისამებრ, თავდაპირველად უნდა გადახედოთ რამდენიმე მაგალითს, სანამ ხსნარში გადავდგებით.

მინიმალური მანძილი BST კვანძებს შორის Leetcode Solution

1

განმარტება: განსხვავება კვანძებს შორის [1, 2], [2, 3], [3, 4], [4, 5] ყველას აქვს სხვაობის 1. და ყველა სხვა წყვილს უფრო დიდი განსხვავება აქვს. ამრიგად, პასუხი არის 1.

უხეში ძალის მიდგომა მინიმალური დაშორებისთვის BST კვანძებს შორის Leetcode Solution

პრობლემა BST კვანძებს შორის მინიმალური მანძილი Leetcode Solution- მა მოგვმართა მოცემული ორობითი ძიების ხეში მინიმალური სხვაობის პოვნა ნებისმიერ ორ კვანძს შორის. ასე რომ, პასუხის პოვნის ერთ-ერთი გზაა BST– ის ნებისმიერი ორი ვერტიკსის ან კვანძის არჩევა და სხვაობის გამოთვლა. ჩვენ განვაახლებთ პასუხს მას შემდეგ, რაც ვიპოვით წყვილს, რომელსაც ნაკლები აბსოლუტური სხვაობა აქვს, ვიდრე წინა წყვილს. თავდაპირველად, შეგვიძლია გამოვიყენოთ ნებისმიერი ორი კვანძი და პროცესის ბოლოს. პასუხი ინახება შესაბამის ცვლადებში. ამ პროცესის სიმულაციისთვის, BST– ს არაორდინალური გზით გადავხედავთ და ვექტორში ვინახავთ. ორი ჩადგმული მარყუჟის გამოყენებით, ჩვენ განვაგრძობთ ხის ყოველ ორ წვერს შორის აბსოლუტური სხვაობის გამოთვლას.

უხეში ძალის კოდექსი

C ++ კოდი მინიმალური მანძილი BST კვანძებს შორის Leetcode Solution

#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 minDiffInBST(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<<minDiffInBST(root);
}
1

Java კოდი მინიმალური მანძილი BST კვანძებს შორის Leetcode Solution

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 minDiffInBST(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(minDiffInBST(root));
  }
}
1

სირთულის ანალიზი

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

O (N ^ 2), ვინაიდან გამოვიყენეთ 2 წყობილი მარყუჟი მინიმალური აბსოლუტური სხვაობის მოსაძებნად, ამ მიდგომის დროის სირთულე მრავალხმიანად იქცევა.

სივრცის სირთულე

O (N), რადგან ჩვენ მოგვიწია შენახვა შეკვეთის გადაკვეთის ვექტორში ან მასივში. ამრიგად, სივრცის სირთულე ხაზოვანია.

ოპტიმიზირებული მიდგომა მინიმალური დაშორებისთვის BST კვანძებს შორის Leetcode Solution

ზემოთ მოყვანილი მიდგომა პრობლემის გადაკვეთის გარეშე. არა მხოლოდ ის იყენებდა შეკვეთის გადაკვეთას, არამედ ასევე ინახავდა მას, რაც O (N) მიდგომას ქმნის სივრცის სირთულის თვალსაზრისით. ჩვენ ასევე არ გამოვიყენეთ ის ფაქტი, რომ BST გვქონდა და მინიმალური აბსოლუტური სხვაობის მიღება შესაძლებელია მხოლოდ ორ ზედიზედ მწვერვალებს შორის. იმის გამო, რომ არ იქნა გათვალისწინებული, ჩვენ გვქონდა პოლინომის დროის სირთულე.

ოპტიმიზირებული მიდგომით, ჩვენ თვალყურს ვადევნებთ წინა კვანძს მიმდინარე წვერზე. ამის გაკეთება გვეხმარება მინიმალური აბსოლუტური სხვაობის პოვნაში შეფასების ოპერაციის მხოლოდ N-1 ჩატარებით. ეს ასევე გვეხმარება მუდმივი სივრცის სირთულის მიღწევაში, რადგან არ გვჭირდება მთელი შეკვეთის შენახვა და მხოლოდ წინა კვანძის შენახვა.

ოპტიმიზირებული კოდი მინიმალური მანძილი BST კვანძებს შორის Leetcode Solution

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 minDiffInBST(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<<minDiffInBST(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 minDiffInBST(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(minDiffInBST(root));
  }
}
1

სირთულის ანალიზი

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

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

სივრცის სირთულე

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