BST లీట్‌కోడ్ పరిష్కారంలో కనీస సంపూర్ణ వ్యత్యాసం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది గూగుల్
ట్రీ

సమస్య BST లీట్‌కోడ్ సొల్యూషన్‌లో కనీస సంపూర్ణ వ్యత్యాసం మీకు అందించబడిందని పేర్కొంది బైనరీ శోధన చెట్టు. మరియు మీరు మొత్తం BST లో కనీస సంపూర్ణ వ్యత్యాసాన్ని కనుగొనవలసి ఉంటుంది. BST లేదా బైనరీ సెర్చ్ ట్రీ అనేది ఒక నియమాన్ని అనుసరించే కొన్ని నోడ్‌లతో కూడిన చెట్టు తప్ప మరొకటి కాదు. నియమం ఏమిటంటే, నోడ్ యొక్క ఎడమ సబ్‌ట్రీ ప్రస్తుత నోడ్ కంటే తక్కువ విలువను కలిగి ఉన్న నోడ్‌లను మాత్రమే కలిగి ఉండాలి. అదేవిధంగా, కుడి సబ్‌ట్రీ కోసం, నోడ్‌లు ప్రస్తుత నోడ్ కంటే ఎక్కువ విలువలను కలిగి ఉండాలి. కాబట్టి, ఎప్పటిలాగే, మేము మొదట పరిష్కారంలోకి దూకడానికి ముందు కొన్ని ఉదాహరణలను పరిశీలించాలి.

BST లీట్‌కోడ్ పరిష్కారంలో కనీస సంపూర్ణ వ్యత్యాసం

1

వివరణ: నోడ్ల మధ్య వ్యత్యాసం [1, 2], [2, 3], [3, 4], [4, 5] అన్నింటికీ 1 తేడా ఉంది. మరియు అన్ని ఇతర జతలకు ఎక్కువ తేడా ఉంది. అందువలన సమాధానం 1.

BST లీట్‌కోడ్ సొల్యూషన్‌లో కనీస సంపూర్ణ వ్యత్యాసం కోసం బ్రూట్ ఫోర్స్ అప్రోచ్

BST లీట్‌కోడ్ సొల్యూషన్‌లో కనీస సంపూర్ణ వ్యత్యాసం ఇచ్చిన బైనరీ సెర్చ్ ట్రీలో ఏదైనా రెండు నోడ్‌ల మధ్య కనీస వ్యత్యాసాన్ని కనుగొనమని కోరింది. కాబట్టి, జవాబును కనుగొనటానికి ఒక మార్గం ఏమిటంటే, BST యొక్క ఏదైనా రెండు శీర్షాలు లేదా నోడ్లను ఎంచుకొని వ్యత్యాసాన్ని లెక్కించడం. మునుపటి జత కంటే తక్కువ సంపూర్ణ వ్యత్యాసం ఉన్న జతను కనుగొన్న తర్వాత మేము సమాధానం అప్‌డేట్ చేస్తాము. ప్రారంభంలో, మేము ఏదైనా రెండు నోడ్లను ఉపయోగించవచ్చు మరియు ప్రక్రియ చివరిలో. సమాధానం సంబంధిత వేరియబుల్స్‌లో నిల్వ చేయబడుతుంది. కాబట్టి, ఈ ప్రక్రియను అనుకరించటానికి, మేము BST ని ఒక క్రమరహిత పద్ధతిలో ప్రయాణించి వెక్టర్‌లో నిల్వ చేస్తాము. రెండు సమూహ ఉచ్చులను ఉపయోగించి, చెట్టులోని ప్రతి రెండు శీర్షాల మధ్య సంపూర్ణ వ్యత్యాసాన్ని లెక్కిస్తూనే ఉంటాము.

బ్రూట్ ఫోర్స్ కోడ్

BST లీట్‌కోడ్ సొల్యూషన్‌లో కనీస సంపూర్ణ వ్యత్యాసం కోసం 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 లీట్‌కోడ్ సొల్యూషన్‌లో కనీస సంపూర్ణ వ్యత్యాసం కోసం జావా కోడ్

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), కనీస సంపూర్ణ వ్యత్యాసాన్ని కనుగొనడానికి మేము 2 సమూహ ఉచ్చులను ఉపయోగించాము కాబట్టి, ఈ విధానం యొక్క సమయ సంక్లిష్టత బహుపది అవుతుంది.

అంతరిక్ష సంక్లిష్టత

పై), ఎందుకంటే మేము ఇన్కార్డర్ ట్రావెర్సల్‌ను వెక్టర్ లేదా శ్రేణిలో నిల్వ చేయాల్సి వచ్చింది. అందువలన, స్థల సంక్లిష్టత సరళంగా ఉంటుంది.

BST లీట్‌కోడ్ సొల్యూషన్‌లో కనీస సంపూర్ణ వ్యత్యాసం కోసం ఆప్టిమైజ్డ్ అప్రోచ్

సమస్యకు పై విధానం BST లీట్‌కోడ్ సొల్యూషన్‌లో కనీస సంపూర్ణ వ్యత్యాసం ఇన్ఆర్డర్ ట్రావెర్సల్‌ను ఉపయోగిస్తుంది. ఇది ఇనార్డర్ ట్రావెర్సల్‌ను ఉపయోగించడమే కాక, దానిని నిల్వ చేసింది, ఇది స్థలం సంక్లిష్టత పరంగా O (N) విధానాన్ని చేస్తుంది. మాకు BST ఉందనే వాస్తవాన్ని కూడా మేము ఉపయోగించలేదు మరియు కనీస సంపూర్ణ వ్యత్యాసం వరుసగా రెండు శీర్షాల మధ్య మాత్రమే పొందవచ్చు. వాస్తవానికి పరిగణనలోకి తీసుకోనందున, మాకు బహుపది సమయ సంక్లిష్టత ఉంది.

ఆప్టిమైజ్ చేసిన విధానంలో, మునుపటి నోడ్‌ను ప్రస్తుత శీర్షానికి ట్రాక్ చేస్తాము. ఇలా చేయడం మూల్యాంకన ఆపరేషన్ N-1 సార్లు మాత్రమే చేయడం ద్వారా కనీస సంపూర్ణ వ్యత్యాసాన్ని కనుగొనడంలో మాకు సహాయపడుతుంది. ఇది స్థిరమైన స్థల సంక్లిష్టతను సాధించడానికి కూడా మాకు సహాయపడుతుంది ఎందుకంటే మేము మొత్తం ఇనార్డర్ ట్రావెర్సల్‌ను నిల్వ చేయవలసిన అవసరం లేదు మరియు మునుపటి నోడ్‌ను మాత్రమే నిల్వ చేస్తాము.

BST లీట్‌కోడ్ సొల్యూషన్‌లో కనీస సంపూర్ణ వ్యత్యాసం కోసం ఆప్టిమైజ్ కోడ్

సి ++ కోడ్

#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 నోడ్ల మీదుగా ప్రయాణించే ఇనార్డర్ ట్రావెర్సల్‌ను మాత్రమే ఉపయోగించాము. అందువలన సమయం సంక్లిష్టత సరళంగా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

ఓ (1), మేము వేరియబుల్స్ యొక్క స్థిరమైన సంఖ్యను మాత్రమే ఉపయోగించాము కాబట్టి. స్థల సంక్లిష్టత కూడా స్థిరమైన స్థలానికి తగ్గించబడింది.