BST लेटकोड समाधानमा न्यूनतम पूर्ण भिन्नता


कठिनाई तह सजिलो
बारम्बार सोधिन्छ गुगल
ट्री

BST लेटकोड समाधानमा समस्या न्यूनतम पूर्ण भिन्नता बताउँछ कि तपाईंलाई a बाइनरी खोज रूख। र तपाईलाई सम्पूर्ण BST मा न्यूनतम निरपेक्ष भिन्नता फेला पार्न आवश्यक छ। एक BST वा बाइनरी खोज ट्री केहि नोडहरूको साथ रूख बाहेक अरू केही हुँदैन जुन नियम अनुसरण गर्दछ। नियम यो हो कि नोडको बायाँ उपशीलनमा केवल नोडहरू मात्र हुनुपर्दछ जुन हालको नोड भन्दा कम मान हुन्छ। त्यस्तै, दाँई सबट्रीका लागि नोडहरूले हालको नोड भन्दा ठूलो मानहरू समावेश गर्न आवश्यक छ। त्यसोभए, सामान्य रूपमा, हामीले समाधानमा हाम फाल्नु अघि केही उदाहरणहरू हेर्नु पर्छ।

BST लेटकोड समाधानमा न्यूनतम पूर्ण भिन्नता

1

स्पष्टीकरण: नोडहरू बीच [१, २], [२,]], [,,]], [,,]] सबैको फरक छ १ र सबै अन्य जोडीसँग ठूलो भिन्नता छ। यसैले उत्तर १ हो।

BST लेटकोड समाधानमा न्यूनतम पूर्ण भिन्नताको लागि ब्रुट फोर्स दृष्टिकोण

BST लेटकोड समाधानमा समस्या न्यूनतम पूर्ण भिन्नता दिइएको बाइनरी खोज रूखमा कुनै पनि दुई नोडहरू बीच न्यूनतम फरक पाउन हामीलाई सोधियो। त्यसोभए, उत्तर पत्ता लगाउने एउटा तरिका BST को कुनै दुई ठाँउ वा नोडहरू छान्नुहोस् र भिन्नता गणना गर्नुहोस्। अघिल्लो जोडी भन्दा कम निरपेक्ष भिन्नता भएको जोडी भेट्टाए पछि हामी उत्तर अपडेट गर्नेछौं। प्रारम्भमा, हामी कुनै पनि दुई नोडहरू प्रयोग गर्न सक्दछौं, र प्रक्रियाको अन्त्यमा। उत्तर सम्बन्धित चरमा भण्डार गरिनेछ। त्यसो भए, यस प्रक्रियाको नक्कल गर्न हामी BST लाई आन्तरिक ढंगले ट्रान्सभर्स गर्नेछौं र यसलाई भेक्टरमा भण्डार गर्नेछौं। दुई नेस्टेड लूपहरू प्रयोग गरेर, हामी रूखमा प्रत्येक दुई शिरको बिचमा पूर्ण भिन्नता गणना गर्न जारी राख्नेछौं।

ब्रुट फोर्स कोड

C ++ कोड BST लेटकोड समाधानमा न्यूनतम पूर्ण भिन्नताको लागि

#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 लेटकोड समाधानमा न्यूनतम पूर्ण भिन्नताको लागि जाभा कोड

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

जटिलता विश्लेषण

समय जटिलता

O (N ^ 2), किनकि हामीले न्यूनतम निरपेक्ष भिन्नता पत्ता लगाउन २ नेस्टेड लूपहरू प्रयोग गरेका छौं, यस दृष्टिकोणको लागि समय जटिलता बहुपद हो।

ठाउँ जटिलता

O (N), किनकि हामीले भेडर वा एर्रेमा ट्रान्सभर्सल इनडोर भण्डार गर्नुपर्‍यो। यसैले, स्पेस जटिलता रैखिक छ।

BST लेटकोड समाधानमा न्यूनतम पूर्ण भिन्नताको लागि अनुकूलित दृष्टिकोण

समस्याको लागि माथिको दृष्टिकोण बीएसटी लेटकोड समाधानमा न्यूनतम पूर्ण भिन्नता प्रयोग गरियो इनडर ट्रभर्सल। यो केवल आन्तरिक traversal मात्र प्रयोग गर्दैन, तर यो पनि यो भण्डारण, अन्तरिक्ष जटिलता को मामला मा दृष्टिकोण O (N) बनाउने। हामीले यस तथ्यलाई पनि प्रयोग गरेनौं कि हामीसँग BST छ, र न्यूनतम निरपेक्ष भिन्नता केवल दुई लगातार चोटीहरू बीच मात्र प्राप्त गर्न सकिन्छ। तथ्यलाई ध्यानमा राखिएको कारणले गर्दा, हामीसँग बहुपद समयको जटिलता थियो।

अनुकूलित दृष्टिकोणमा, हामी हालको भर्टेक्समा अघिल्लो नोडको ट्र्याक राख्छौं। यो गर्नाले हामीलाई मूल्या operation्कन अपरेसन केवल N-1 पटक प्रदर्शन गरेर न्यूनतम निरपेक्ष भिन्नता फेला पार्न मद्दत गर्दछ। यसले हामीलाई स्थिर स्थान जटिलता प्राप्त गर्न पनि मद्दत गर्दछ किनकि हामीसँग सम्पूर्ण ईन्डर ट्रभर्सल भण्डार गर्नुपर्दैन, र अघिल्लो नोड मात्र भण्डारण गर्नुपर्दैन।

BST लेटकोड समाधानमा न्यूनतम पूर्ण भिन्नताको लागि अनुकूलित कोड

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

जटिलता विश्लेषण

समय जटिलता

O (N), किनकि हामीले केवल ईन्टरर ट्रभर्सल प्रयोग गर्यौं जुन रूखमा N नोडहरू माथि पार गर्दछ। यस प्रकार समय जटिलता रैखिक छ।

ठाउँ जटिलता

O (१), किनकि हामी चलहरूको स्थिर संख्या मात्र प्रयोग गर्दछौं। अन्तरिक्ष जटिलता स्थिर स्थानमा पनि कम भयो।