Мінімальная адлегласць паміж вузламі BST Рашэнне Leetcode


Узровень складанасці Лёгка
Часта пытаюцца ў Google
Рэкурсія дрэва

Праблема Мінімальная адлегласць паміж вузламі BST з рашэннем штрых-кода абвяшчае, што вам прадастаўлена двайковае дрэва пошуку. І вы павінны знайсці мінімальную розніцу ў цэлым BST. Такім чынам, вам трэба знайсці мінімальную абсалютную розніцу паміж любымі двума вузламі ў BST. BST або двайковае дрэва пошуку - гэта не што іншае, як дрэва з некалькімі вузламі, якія выконваюць правіла. правіла заключаецца ў тым, што левае паддрэва вузла павінна ўтрымліваць толькі тыя вузлы, якія маюць значэнне, меншае за бягучы вузел. Аналагічна, для правага паддрэва вузлы павінны ўтрымліваць значэнні, большыя за бягучы вузел. Такім чынам, як звычайна, мы павінны спачатку зірнуць на некалькі прыкладаў, перш чым пераходзіць да вырашэння.

Мінімальная адлегласць паміж вузламі BST Рашэнне Leetcode

1

Тлумачэнне: розніца паміж вузламі [1, 2], [2, 3], [3, 4], [4, 5] мае розніцу ў 1. А ва ўсіх астатніх пар розніца большая. Такім чынам, адказ 1.

Падыход грубай сілы для мінімальнай адлегласці паміж вузламі BST Рашэнне з выкарыстаннем літаркода

Праблема Мінімальная адлегласць паміж вузламі BST Рашэнне Leetcode прапанавала нам знайсці мінімальную розніцу паміж любымі двума вузламі ў дадзеным двайковым дрэве пошуку. Такім чынам, адзін са спосабаў знайсці адказ - выбраць любыя дзве вяршыні або вузлы 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 укладзеныя цыклы, каб знайсці мінімальную абсалютную розніцу, складанасць часу для гэтага падыходу становіцца мнагачленнай.

Касмічная складанасць

O (N), таму што нам трэба было захоўваць унутраны абход у вектары ці масіве. Такім чынам, касмічная складанасць лінейная.

Аптымізаваны падыход для мінімальнай адлегласці паміж вузламі BST

Вышэйапісаны падыход да праблемы ў абходным парадку. Ён не толькі выкарыстаў парадак абходу, але і захаваў яго, зрабіўшы падыход O (N) з пункту гледжання касмічнай складанасці. Мы таксама не выкарыстоўвалі той факт, што ў нас была BST, і мінімальная абсалютная розніца можа быць атрымана толькі паміж двума паслядоўнымі вяршынямі. З-за таго, што факт не ўлічваўся, мы мелі шматчленную складанасць часу.

Пры аптымізаваным падыходзе мы адсочваем папярэдні вузел да бягучай вяршыні. Гэта дапамагае нам знайсці мінімальную абсалютную розніцу, выконваючы аперацыю ацэнкі толькі N-1 раз. Гэта таксама дапамагае нам дасягаць пастаяннай складанасці ў прасторы, таму што нам не трэба захоўваць увесь унутраны абход, а толькі папярэдні вузел.

Аптымізаваны код для мінімальнай адлегласці паміж вузламі BST

Код 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), паколькі мы выкарыстоўвалі толькі пастаянную колькасць зменных. Касмічная складанасць таксама зводзіцца да пастаяннай прасторы.