ಬಿಎಸ್ಟಿ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಗೂಗಲ್
ಮರ

ಬಿಎಸ್ಟಿ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿನ ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸವು ನಿಮಗೆ ಒದಗಿಸಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ. ಮತ್ತು ಸಂಪೂರ್ಣ ಬಿಎಸ್‌ಟಿಯಲ್ಲಿ ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸವನ್ನು ನೀವು ಕಂಡುಹಿಡಿಯಬೇಕು. ಬಿಎಸ್ಟಿ ಅಥವಾ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ನಿಯಮವನ್ನು ಅನುಸರಿಸುವ ಕೆಲವು ನೋಡ್ಗಳನ್ನು ಹೊಂದಿರುವ ಮರವಲ್ಲ. ನಿಯಮವೆಂದರೆ ನೋಡ್‌ನ ಎಡ ಸಬ್‌ಟ್ರೀ ಪ್ರಸ್ತುತ ನೋಡ್‌ಗಿಂತ ಕಡಿಮೆ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುವ ನೋಡ್‌ಗಳನ್ನು ಮಾತ್ರ ಹೊಂದಿರಬೇಕು. ಅಂತೆಯೇ, ಸರಿಯಾದ ಸಬ್‌ಟ್ರೀಗಾಗಿ, ನೋಡ್‌ಗಳು ಪ್ರಸ್ತುತ ನೋಡ್‌ಗಿಂತ ಹೆಚ್ಚಿನ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರಬೇಕು. ಆದ್ದರಿಂದ, ಎಂದಿನಂತೆ, ನಾವು ಮೊದಲು ಪರಿಹಾರಕ್ಕೆ ಹಾರಿ ಮೊದಲು ಕೆಲವು ಉದಾಹರಣೆಗಳನ್ನು ನೋಡಬೇಕು.

ಬಿಎಸ್ಟಿ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸ

1

ವಿವರಣೆ: ನೋಡ್‌ಗಳ ನಡುವಿನ ವ್ಯತ್ಯಾಸ [1, 2], [2, 3], [3, 4], [4, 5] ಎಲ್ಲವೂ 1 ರ ವ್ಯತ್ಯಾಸವನ್ನು ಹೊಂದಿವೆ. ಮತ್ತು ಇತರ ಎಲ್ಲ ಜೋಡಿಗಳು ಹೆಚ್ಚಿನ ವ್ಯತ್ಯಾಸವನ್ನು ಹೊಂದಿವೆ. ಹೀಗೆ ಉತ್ತರ 1.

ಬಿಎಸ್ಟಿ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸಕ್ಕಾಗಿ ಬ್ರೂಟ್ ಫೋರ್ಸ್ ಅಪ್ರೋಚ್

ನಿರ್ದಿಷ್ಟ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀನಲ್ಲಿ ಯಾವುದೇ ಎರಡು ನೋಡ್ಗಳ ನಡುವಿನ ಕನಿಷ್ಠ ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಬಿಎಸ್ಟಿ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿನ ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸವು ನಮ್ಮನ್ನು ಕೇಳಿದೆ. ಆದ್ದರಿಂದ, ಉತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಒಂದು ಮಾರ್ಗವೆಂದರೆ ಬಿಎಸ್‌ಟಿಯ ಯಾವುದೇ ಎರಡು ಶೃಂಗಗಳು ಅಥವಾ ನೋಡ್‌ಗಳನ್ನು ಆರಿಸಿ ಮತ್ತು ವ್ಯತ್ಯಾಸವನ್ನು ಲೆಕ್ಕಹಾಕುವುದು. ಹಿಂದಿನ ಜೋಡಿಗಿಂತ ಕಡಿಮೆ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸವನ್ನು ಹೊಂದಿರುವ ಜೋಡಿಯನ್ನು ನಾವು ಕಂಡುಕೊಂಡ ನಂತರ ನಾವು ಉತ್ತರವನ್ನು ನವೀಕರಿಸುತ್ತೇವೆ. ಆರಂಭದಲ್ಲಿ, ನಾವು ಯಾವುದೇ ಎರಡು ನೋಡ್‌ಗಳನ್ನು ಬಳಸಬಹುದು, ಮತ್ತು ಪ್ರಕ್ರಿಯೆಯ ಕೊನೆಯಲ್ಲಿ. ಉತ್ತರವನ್ನು ಆಯಾ ಅಸ್ಥಿರಗಳಲ್ಲಿ ಸಂಗ್ರಹಿಸಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ, ಈ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಅನುಕರಿಸಲು, ನಾವು ಬಿಎಸ್ಟಿಯನ್ನು ಅನಿಯಮಿತ ರೀತಿಯಲ್ಲಿ ಹಾದುಹೋಗುತ್ತೇವೆ ಮತ್ತು ಅದನ್ನು ವೆಕ್ಟರ್ನಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ. ಎರಡು ನೆಸ್ಟೆಡ್ ಲೂಪ್‌ಗಳನ್ನು ಬಳಸಿ, ಮರದ ಪ್ರತಿಯೊಂದು ಎರಡು ಶೃಂಗಗಳ ನಡುವಿನ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸವನ್ನು ನಾವು ಲೆಕ್ಕ ಹಾಕುತ್ತೇವೆ.

ವಿವೇಚನಾರಹಿತ ಶಕ್ತಿ ಕೋಡ್

ಬಿಎಸ್ಟಿ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸಕ್ಕಾಗಿ ಸಿ ++ ಕೋಡ್

#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

ಬಿಎಸ್ಟಿ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸಕ್ಕಾಗಿ ಜಾವಾ ಕೋಡ್

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 ನೆಸ್ಟೆಡ್ ಲೂಪ್‌ಗಳನ್ನು ಬಳಸಿದ್ದರಿಂದ, ಈ ವಿಧಾನದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಬಹುಪದೀಯವಾಗುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ಇನಾಡರ್ ಟ್ರಾವೆರ್ಸಲ್ ಅನ್ನು ವೆಕ್ಟರ್ ಅಥವಾ ಅರೇನಲ್ಲಿ ಸಂಗ್ರಹಿಸಬೇಕಾಗಿತ್ತು. ಹೀಗಾಗಿ, ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

ಬಿಎಸ್ಟಿ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸಕ್ಕಾಗಿ ಆಪ್ಟಿಮೈಸ್ಡ್ ಅಪ್ರೋಚ್

ಸಮಸ್ಯೆಗೆ ಮೇಲಿನ ವಿಧಾನ ಬಿಎಸ್ಟಿ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿನ ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸವು ಇನಾರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್ ಅನ್ನು ಬಳಸುತ್ತದೆ. ಇದು ಇನಾರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್ ಅನ್ನು ಬಳಸಿದ್ದಲ್ಲದೆ, ಅದನ್ನು ಸಂಗ್ರಹಿಸಿ, ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯ ದೃಷ್ಟಿಯಿಂದ ಒ (ಎನ್) ವಿಧಾನವನ್ನು ಮಾಡುತ್ತದೆ. ನಾವು ಬಿಎಸ್ಟಿ ಹೊಂದಿದ್ದೇವೆ ಎಂಬ ಅಂಶವನ್ನೂ ನಾವು ಬಳಸಲಿಲ್ಲ, ಮತ್ತು ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸವನ್ನು ಸತತ ಎರಡು ಶೃಂಗಗಳ ನಡುವೆ ಮಾತ್ರ ಪಡೆಯಬಹುದು. ವಾಸ್ತವವಾಗಿ ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳದ ಕಾರಣ, ನಾವು ಬಹುಪದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿದ್ದೇವೆ.

ಆಪ್ಟಿಮೈಸ್ಡ್ ವಿಧಾನದಲ್ಲಿ, ನಾವು ಹಿಂದಿನ ನೋಡ್ ಅನ್ನು ಪ್ರಸ್ತುತ ಶೃಂಗಕ್ಕೆ ಟ್ರ್ಯಾಕ್ ಮಾಡುತ್ತೇವೆ. ಇದನ್ನು ಮಾಡುವುದರಿಂದ ಮೌಲ್ಯಮಾಪನ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಕೇವಲ N-1 ಬಾರಿ ಮಾಡುವ ಮೂಲಕ ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಮಗೆ ಸಹಾಯ ಮಾಡುತ್ತದೆ. ಸ್ಥಿರವಾದ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯನ್ನು ಸಾಧಿಸಲು ಇದು ನಮಗೆ ಸಹಾಯ ಮಾಡುತ್ತದೆ ಏಕೆಂದರೆ ನಾವು ಸಂಪೂರ್ಣ ಇನಾರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್ ಅನ್ನು ಸಂಗ್ರಹಿಸಬೇಕಾಗಿಲ್ಲ ಮತ್ತು ಹಿಂದಿನ ನೋಡ್ ಅನ್ನು ಮಾತ್ರ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ.

ಬಿಎಸ್ಟಿ ಲೀಟ್ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಕನಿಷ್ಠ ಸಂಪೂರ್ಣ ವ್ಯತ್ಯಾಸಕ್ಕಾಗಿ ಆಪ್ಟಿಮೈಸ್ಡ್ ಕೋಡ್

ಸಿ ++ ಕೋಡ್

#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), ನಾವು ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಅಸ್ಥಿರಗಳನ್ನು ಮಾತ್ರ ಬಳಸಿದ್ದರಿಂದ. ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯು ಸ್ಥಿರ ಸ್ಥಳಕ್ಕೆ ಕಡಿಮೆಯಾಗಿದೆ.