Масофаи ҳадди аққал дар байни гиреҳҳои BST Solution Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Google
Барқароркунӣ Дарахт

Масъалаи ҳадди аққал байни гиреҳҳои BST Leetcode Solution изҳор медорад, ки ба шумо дарахти ҷустуҷӯи бинарӣ дода шудааст. Ва аз шумо талаб карда мешавад, ки фарқи ҳадди ақаллро дар маҷмӯъ пайдо кунед БАС. Ҳамин тавр, шумо бояд фарқи ҳадди ақали мутлақро байни ҳарду гиреҳ дар BST ёбед. Дарахти ҷустуҷӯи BST ё дуӣ чизе нест, ҷуз дарахтест бо баъзе гиреҳҳо, ки аз рӯи қоида амал мекунанд. қоида ин аст, ки дар зери дарахти чапи гиреҳ бояд танҳо гиреҳҳо бошанд, ки арзишашон аз гиреҳи ҷорӣ камтар бошад. Ба ҳамин монанд, барои зергурӯҳи дуруст гиреҳҳо бояд қиматҳоро аз гиреҳи кунунӣ бештар дошта бошанд. Пас, одатан, пеш аз он ки ба ҳалли худ ҷаҳем, мо бояд аввал якчанд мисолро дида бароем.

Масофаи ҳадди аққал дар байни гиреҳҳои BST Solution Leetcode

1

Шарҳ: Фарқи байни гиреҳҳо [1, 2], [2, 3], [3, 4], [4, 5] ҳама фарқияти 1 доранд. Ва ҳамаи ҷуфтҳои дигар фарқи калонтар доранд. Ҳамин тавр ҷавоб 1 аст.

Усули қувваи бераҳмона барои масофаи ҳадди ақалл дар байни BST гиреҳҳои Solution Leetcode

Масъалаи ҳадди аққал байни гиреҳҳои BST Leetcode Solution аз мо хоҳиш кард, ки фарқи ҳадди аққал байни ҳарду гиреҳро дар як дарахти ҷустуҷӯи бинарӣ пайдо кунем. Ҳамин тавр, як роҳи ёфтани ҷавоб ин интихоб кардани ҳар гуна ду қулла ё гиреҳи БСТ ва ҳисоб кардани фарқият аст. Пас аз пайдо кардани ҷуфте, ки фарқи мутлақ нисбат ба ҷуфти қаблӣ камтар аст, ҷавобро нав хоҳем кард. Дар аввал, мо метавонем ҳар ду гиреҳро истифода барем ва дар охири раванд. Ҷавоб дар тағирёбандаҳои дахлдор ҳифз карда мешавад. Ҳамин тавр, барои симулятсияи ин раванд, мо 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 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 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 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

Таҳлили мураккабӣ

Мураккабии вақт

О (N ^ 2), азбаски мо барои ёфтани фарқияти ҳадди ақали мутлақ аз 2 ҳалқаи лона истифода кардем, мураккабии вақт барои ин равиш полиномия мешавад.

Мураккабии фазо

О (Н), зеро мо маҷбур шудем, ки гардиши inorder-ро дар вектор ё массив нигоҳ дорем. Ҳамин тариқ, мураккабии фазо хаттӣ аст.

Усули беҳтарин барои масофаи ҳадди аққал байни BST гиреҳҳои Solution Leetcode

Усули дар боло зикршуда барои гузариши мушкилот. Он на танҳо дар гузариши inorder истифода кард, балки онро низ нигоҳ дошт ва муносибати 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 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

Таҳлили мураккабӣ

Мураккабии вақт

О (Н), азбаски мо танҳо гузариши inorder истифода мекардем, ки аз болои гиреҳҳои дарахт мегузашт. Ҳамин тавр мураккабии вақт хатӣ аст.

Мураккабии фазо

О (1), зеро мо танҳо шумораи доимии тағирёбандаҳоро истифода мебурдем. Мураккабии фазо низ ба фазои доимӣ коҳиш ёфт.