BST зангилааны хоорондох хамгийн бага зай Leetcode шийдэл


Хэцүү байдлын түвшин Easy
Байнга асуудаг Google-ийн
Сэтгэгдэл бичих Мод

BST зангилааны хоорондох хамгийн бага зай Leetcode шийдлийн асуудал нь танд хоёртын хайлтын модоор хангагдсан болохыг харуулж байна. Хамгийн бага зөрүүг бүхэлд нь олох шаардлагатай BST. Тиймээс, та BST дээрх хоёр зангилааны хоорондох хамгийн бага үнэмлэхүй ялгааг олох хэрэгтэй. BST эсвэл Binary Search Tree нь дүрмийг дагаж мөрддөг зарим зангилаа бүхий модноос өөр зүйл биш юм. дүрэм бол зангилааны зүүн дэд мод нь зөвхөн одоогийн зангилаанаас бага утгатай зангилааг агуулсан байх ёстой. Үүнтэй адилаар баруун дэд модны хувьд зангилаа нь одоогийн зангилаанаас их утгыг агуулсан байх ёстой. Тиймээс, ердийн байдлаар бид эхлээд уусмал руу үсрэхээсээ өмнө хэдэн жишээг авч үзэх хэрэгтэй.

BST зангилааны хоорондох хамгийн бага зай Leetcode шийдэл

1

Тайлбар: Зангилааны ялгаа [1, 2], [2, 3], [3, 4], [4, 5] бүгд 1-ийн зөрүүтэй байна. Бусад бүх хосууд илүү их зөрүүтэй байна. Тиймээс хариулт нь 1 байна.

BST зангилааны Leetcode шийдлийн хоорондох хамгийн бага зай дахь хүчирхийллийн хүчний арга

BST зангилааны хоорондох хамгийн бага зай Leetcode шийдэл нь өгөгдсөн хоёртын хайлтын модны аль ч хо nр зангилааны хоорондох хамгийн бага зөрүүг олохыг хүссэн. Тиймээс хариултыг олох нэг арга бол БСТ-ийн дурын хоёр орой буюу зангилааг сонгож, зөрүүг тооцох явдал юм. Өмнөх хосуудтай харьцуулахад үнэмлэхүй ялгаа багатай хосыг олсны дараа бид хариултаа шинэчлэх болно. Эхний ээлжинд бид үйл явцын төгсгөлд дурын хоёр зангилааг ашиглаж болно. Хариулт нь тухайн хувьсагчид хадгалагдах болно. Тиймээс энэ үйл явцыг дууриахын тулд BST-ийг тохиромжгүй байдлаар туулж вектороор хадгалах болно. Хоёр үүрлэсэн гогцоог ашиглан бид модны хоёр орой бүрийн үнэмлэхүй ялгааг үргэлжлүүлэн тооцоолсоор байх болно.

Харгис хүчний код

BST цэгүүдийн Leetcode шийдлийн хоорондох хамгийн бага зайны C ++ код

#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

BST зангилааны хоорондох хамгийн бага зайны Leetcode шийдлийн Java код

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 үүрлэсэн гогцоог ашигласан тул энэ хандлагын хугацааны нарийн төвөгтэй байдал нь олон гишүүнт болж хувирдаг.

Сансрын нарийн төвөгтэй байдал

O (N), учир нь бид inorder traversal-ийг вектор эсвэл массивт хадгалах ёстой байв. Тиймээс орон зайн нарийн төвөгтэй байдал нь шугаман юм.

BST зангилааны хоорондох хамгийн бага зайны оновчтой хандлага Leetcode шийдэл

Асуудлыг хөндлөн гарахад чиглэсэн дээрх хандлага. Энэ нь зөвхөн inorder traversal ашигласан төдийгүй үүнийг хадгалж, орон зайн нарийн төвөгтэй байдлын хувьд 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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N)Учир нь бид модон дээрх N зангилаан дээгүүр дайрч өнгөрдөг байсан. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь шугаман юм.

Сансрын нарийн төвөгтэй байдал

O (1), бид зөвхөн тогтмол тооны хувьсагч ашигладаг байсан тул. Сансрын нарийн төвөгтэй байдал нь тогтмол орон зайд хүртэл буурсан.