Минимална абсолютна разлика в BST Leetcode Solution


Ниво на трудност Лесно
Често задавани в Google
Дърво

Проблемът Минимална абсолютна разлика в BST Leetcode Solution гласи, че сте получили a Двоично дърво за търсене. И от вас се изисква да намерите минималната абсолютна разлика в целия BST. BST или двоично дърво за търсене не е нищо друго освен дърво с някои възли, които следват правило. правилото е, че лявото поддърво на възел трябва да съдържа само възлите, които имат стойност по-малка от текущия възел. По същия начин, за дясното поддърво, възлите трябва да съдържат стойности, по-големи от текущия възел. Така че, както обикновено, първо трябва да разгледаме няколко примера, преди да преминем към решението.

Минимална абсолютна разлика в BST Leetcode Solution

1

Обяснение: Разликата между възлите [1, 2], [2, 3], [3, 4], [4, 5] всички имат разлика от 1. И всички други двойки имат по-голяма разлика. По този начин отговорът е 1.

Подход на грубата сила за минимална абсолютна разлика в BST Leetcode Solution

Проблемът Минимална абсолютна разлика в BST Leetcode Solution ни помоли да намерим минималната разлика между всеки два възела в дадено двоично дърво за търсене. Така че, един от начините за намиране на отговора е да изберете произволни два върха или възли на BST и да изчислите разликата. Ще актуализираме отговора, след като намерим двойка, която има по-малка абсолютна разлика от предишната двойка. Първоначално можем да използваме всеки два възела и в края на процеса. Отговорът ще се съхранява в съответните променливи. Така че, за да симулираме този процес, ние ще преминем BST по неподходящ начин и ще го съхраним във вектор. Използвайки два вложени цикъла, ще продължим да изчисляваме абсолютната разлика между всеки два върха в дървото.

Кодекс на грубата сила

C ++ код за минимална абсолютна разлика в BST Leetcode Solution

#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

Java код за минимална абсолютна разлика в 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

Анализ на сложността

Сложност във времето

O (N ^ 2), тъй като сме използвали 2 вложени цикъла, за да намерим минималната абсолютна разлика, сложността във времето за този подход става полином.

Сложност на пространството

НА), защото трябваше да съхраняваме обхождането на inorder във вектор или масив. По този начин космическата сложност е линейна.

Оптимизиран подход за минимална абсолютна разлика в BST Leetcode Solution

Горният подход за проблема Минимална абсолютна разлика в BST Leetcode Solution, използван при обръщане на поръчка. той не само е използвал при обръщане, но и го е съхранил, като е направил подхода O (N) от гледна точка на космическата сложност. Също така не използвахме факта, че имахме BST и минималната абсолютна разлика може да бъде получена само между два последователни върха. Поради факта, че не е взето предвид, имахме полиномиална времева сложност.

В оптимизирания подход ние следим предишния възел до текущия връх. Това ни помага да намерим минималната абсолютна разлика, като извършваме операция за оценка само 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

Java код

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 възлите на дървото. По този начин сложността на времето е линейна.

Сложност на пространството

O (1), тъй като използвахме само постоянен брой променливи. Сложността на пространството също се свежда до постоянно пространство.