BST Leetcode Solution में न्यूनतम निरपेक्ष अंतर


कठिनाई स्तर आसान
में अक्सर पूछा गूगल
पेड़

BST Leetcode Solution में समस्या न्यूनतम निरपेक्षता अंतर बताती है कि आपको प्रदान किया गया है बाइनरी सर्च ट्री। और आपको पूरे BST में न्यूनतम पूर्ण अंतर खोजने की आवश्यकता है। BST या बाइनरी सर्च ट्री कुछ नहीं बल्कि कुछ नोड्स वाला पेड़ है जो एक नियम का पालन करते हैं। नियम यह है कि एक नोड के बाएं सबट्री में केवल वे नोड होते हैं जिनका मूल्य वर्तमान नोड से कम है। इसी तरह, सही सबट्री के लिए, नोड्स में वर्तमान नोड से अधिक मान होना चाहिए। इसलिए, हमेशा की तरह, हमें समाधान में कूदने से पहले कुछ उदाहरणों पर ध्यान देना चाहिए।

BST Leetcode Solution में न्यूनतम निरपेक्ष अंतर

1

स्पष्टीकरण: नोड्स के बीच अंतर [1, 2], [2, 3], [3, 4], [4, 5] सभी में 1. का अंतर है और अन्य सभी जोड़े में अधिक अंतर है। इस प्रकार उत्तर 1 है।

बीएसटी लेकोडकोड समाधान में न्यूनतम पूर्ण अंतर के लिए ब्रूट फोर्स दृष्टिकोण

BST Leetcode Solution में समस्या न्यूनतम निरपेक्ष अंतर ने हमें किसी दिए गए बाइनरी सर्च ट्री में किसी भी दो नोड्स के बीच न्यूनतम अंतर खोजने के लिए कहा। तो, उत्तर खोजने का एक तरीका बीएसटी के किसी भी दो कोने या नोड को चुनना है और अंतर की गणना करना है। एक जोड़ी मिलने पर हम उत्तर को अपडेट करेंगे, जिसमें पिछली जोड़ी की तुलना में कम पूर्ण अंतर है। प्रारंभ में, हम किसी भी दो नोड्स का उपयोग कर सकते हैं, और प्रक्रिया के अंत में। उत्तर संबंधित चर में संग्रहीत किया जाएगा। इसलिए, इस प्रक्रिया को अनुकरण करने के लिए, हम बीएसटी को एक इनवर्टर तरीके से पार करेंगे और इसे वेक्टर में स्टोर करेंगे। दो नेस्टेड छोरों का उपयोग करते हुए, हम पेड़ में हर दो कोने के बीच पूर्ण अंतर की गणना करते रहेंगे।

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

BST Leetcode Solution में न्यूनतम निरपेक्ष अंतर के लिए C ++ कोड

#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 में न्यूनतम निरपेक्ष अंतर के लिए जावा कोड

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

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

समय जटिलता

ओ (एन ^ 2), चूंकि हमने न्यूनतम निरपेक्ष अंतर को खोजने के लिए 2 नेस्टेड छोरों का उपयोग किया है, इस दृष्टिकोण के लिए समय की जटिलता बहुपद बन जाती है।

अंतरिक्ष जटिलता

पर), क्योंकि हमें इन्वर्टर ट्रैवर्सल को वेक्टर या एरे में स्टोर करना था। इस प्रकार, अंतरिक्ष जटिलता रैखिक है।

BST Leetcode Solution में न्यूनतम निरपेक्ष अंतर के लिए अनुकूलित दृष्टिकोण

समस्या के लिए उपरोक्त दृष्टिकोण बीटीएस लेटकोड सॉल्यूशन में न्यूनतम पूर्ण अंतर इनवर्टर ट्रैवर्सल का उपयोग किया गया है। न केवल इसमें इनवर्टर ट्रैवर्सल का उपयोग किया गया, बल्कि इसने इसे संग्रहीत भी किया, जिससे अंतरिक्ष जटिलता के संदर्भ में दृष्टिकोण O (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 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

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

समय जटिलता

पर), चूँकि हमने केवल इनवर्टर ट्रैवर्सल का उपयोग किया था जो पेड़ पर एन नोड्स पर ट्रेस किया गया था। इस प्रकार समय जटिलता रैखिक है।

अंतरिक्ष जटिलता

ओ (1), चूँकि हम केवल निरंतर संख्या में चर का उपयोग करते थे। अंतरिक्ष की जटिलता भी निरंतर स्थान तक कम हो गई।