बीएसटी नोड्स लेकोडकोड समाधान के बीच न्यूनतम दूरी


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

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

बीएसटी नोड्स लेकोडकोड समाधान के बीच न्यूनतम दूरी

1

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

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

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

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

B ++ नोड्स लेकोडकोड समाधान के बीच न्यूनतम दूरी के लिए 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 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

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 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

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

समय जटिलता

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

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

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

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

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

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

समय जटिलता

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

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

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