Минимално разстояние между BST възли Leetcode решение


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

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

Минимално разстояние между BST възли Leetcode решение

1

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

Подход на груба сила за минимално разстояние между BST възли Leetcode решение

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

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

C ++ код за минимално разстояние между BST възли Leetcode решение

#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

Java код за минимално разстояние между BST възли Leetcode решение

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

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

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

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

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

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

Оптимизиран подход за минимално разстояние между BST възли Leetcode решение

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

В оптимизирания подход ние следим предишния възел до текущия връх. Това ни помага да намерим минималната абсолютна разлика, като извършваме операция за оценка само N-1 пъти. Това също ни помага да постигнем постоянна сложност в пространството, защото не е нужно да съхраняваме цялото вътрешно обхождане и да съхраняваме само предишния възел.

Оптимизиран код за минимално разстояние между BST възли Leetcode решение

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

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

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

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

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

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

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