Минимална апсолутна разлика во решението за лек-код BST


Ниво на тешкотија Лесно
Често прашувано во Google
Дрво

Проблемот Минимална апсолутна разлика во решението за лек кодови во БСТ наведува дека ви се обезбедува а Дрво за бинарно пребарување. И од вас се бара да ја пронајдете минималната апсолутна разлика во целиот БСТ. Дрво за BST или бинарно пребарување не е ништо друго освен дрво со некои јазли што следат правило. правилото е дека левото под-дрво на јазол мора да содржи само јазли кои имаат вредност помала од тековниот јазол. Слично на тоа, за десното под дрво, јазлите мора да содржат вредности поголеми од тековниот јазол. Значи, како и обично, прво мора да разгледаме неколку примери пред да скокнеме во решението.

Минимална апсолутна разлика во решението за лек-код BST

1

Објаснување: Разликата помеѓу јазлите [1, 2], [2, 3], [3, 4], [4, 5] сите имаат разлика од 1. И сите други парови имаат поголема разлика. Така, одговорот е 1.

Пристап на брутална сила за минимална апсолутна разлика во решението за леткод на BST

Проблемот Минимална апсолутна разлика во решението за лек кодови во BST не замоли да најдеме минимална разлика помеѓу кој било два јазли во даденото дрво за бинарно пребарување. Значи, еден начин да се најде одговорот е да се изберат какви било две темиња или јазли на BST и да се пресмета разликата. Одговорот ќе го ажурираме откако ќе најдеме пар кој има помала апсолутна разлика од претходниот пар. Првично, можеме да користиме кои било два јазли, и на крајот од процесот. Одговорот ќе биде зачуван во соодветните променливи. Значи, за да го симулираме овој процес, ние ќе го поминеме BST на неправилен начин и ќе го зачуваме во вектор. Користејќи две вгнездени јамки, ќе продолжиме да ја пресметуваме апсолутната разлика помеѓу секои две темиња на дрвото.

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

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

#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

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

Временска комплексност

О (N ^ 2), бидејќи користевме 2 вгнездени јамки за да ја пронајдеме минималната апсолутна разлика, временската сложеност за овој пристап станува полином.

Комплексноста на просторот

НА), затоа што требаше да ја складираме непрегледната траверсал во вектор или низа. Така, вселенската комплексност е линеарна.

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

Горенаведениот пристап за проблемот Минимална апсолутна разлика во растворот за Leetcode во BST користен пресек на редот. не само што користеше пониска траверза, туку и ја чуваше, правејќи го пристапот О (Н) во однос на комплексноста на просторот. Ние исто така не го користевме фактот дека имавме BST, а минималната апсолутна разлика може да се добие само помеѓу две последователни темиња. Бидејќи не се земени предвид, имавме полиномна временска сложеност.

Во оптимизираниот пристап, го следиме претходниот јазол до тековното теме. Правејќи го ова, ни помага да ја најдеме минималната апсолутна разлика, извршувајќи операција за проценка само N-1 пати. Ова исто така ни помага да постигнеме постојана комплексност во вселената затоа што не мора да ја складираме целата пониска трага и да го чуваме само претходниот јазол.

Оптимизиран код за минимална апсолутна разлика во решението за BET 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 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

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

Временска комплексност

НА), бидејќи користевме само вонредна поминување што минуваше низ Н-јазлите на дрвото. Така, временската сложеност е линеарна.

Комплексноста на просторот

О (1), бидејќи користевме само постојан број на променливи. Комплексноста на вселената исто така се сведе на постојан простор.