BST Leetcode шийдлийн хамгийн бага үнэмлэхүй ялгаа


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

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

BST Leetcode шийдлийн хамгийн бага үнэмлэхүй ялгаа

1

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

BST Leetcode шийдлийн хамгийн бага үнэмлэхүй ялгааг харгис хэрцгий аргаар ашиглах арга

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

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

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

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

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

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

Асуудлын талаархи дээрх хандлага нь BEST Leetcode Solution-ийн хамгийн бага үнэмлэхүй ялгаа. inorder traversal-ийг ашиглаад зогсохгүй сансрын нарийн төвөгтэй байдлын хувьд 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

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

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

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

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

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