Leftcode шешімінің BST түйіндері арасындағы минималды арақашықтық


Күрделілік дәрежесі оңай
Жиі кіреді Google
Рекурсия ағаш

Lextcode Solution түйіндерінің арасындағы минималды арақашықтық проблемасы сізге екілік іздеу ағашын ұсынғанын айтады. Сізден тұтастай алғанда ең аз айырмашылықты табу қажет BST. Сонымен, сізге БСТ кез-келген екі түйін арасындағы минималды абсолютті айырмашылықты табу керек. BST немесе екілік іздеу ағашы - бұл ережеге сәйкес келетін кейбір түйіндері бар ағаштан басқа ештеңе емес. ереже - түйіннің сол жақ тармақшасында мәні тек ағымдағы түйіннен аз түйіндер болуы керек. Сол сияқты, дұрыс ішкі ағаш үшін түйіндерде ағымдағы түйіннен үлкен мәндер болуы керек. Сонымен, әдеттегідей, біз шешімге секірмес бұрын алдымен бірнеше мысалға назар аударуымыз керек.

Leftcode шешімінің BST түйіндері арасындағы минималды арақашықтық

1

Түсініктеме: [1, 2], [2, 3], [3, 4], [4, 5] түйіндерінің айырмашылығы 1-ге тең, ал қалған жұптардың айырмашылығы үлкен. Осылайша жауап 1 болады.

BST түйіндері арасындағы минималды арақашықтыққа қатысты күш қолдану тәсілі Leetcode шешімі

BST түйіндерінің арасындағы минималды арақашықтық Leetcode Solution берілген екілік іздеу ағашындағы кез-келген екі түйін арасындағы минималды айырмашылықты табуды сұрады. Сонымен, жауап табудың бір жолы - БСТ кез-келген екі төбесін немесе түйінін таңдау және айырмашылықты есептеу. Алдыңғы жұпқа қарағанда абсолюттік айырмашылығы азырақ жұпты тапқаннан кейін жауабын жаңартамыз. Бастапқыда біз кез-келген екі түйінді қолдана аламыз және процестің соңында. Жауап тиісті айнымалыларда сақталады. Сонымен, бұл процесті модельдеу үшін біз BST-ді инертті түрде өтіп, оны векторда сақтаймыз. Екі кірістірілген ілмекті қолданып, біз ағаштың әр екі төбесінің арасындағы абсолютті айырмашылықты есептей береміз.

Дөрекі күш кодексі

BST түйіндері арасындағы ең аз арақашықтыққа арналған C ++ коды 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

BST түйіндері арасындағы минималды арақашықтық үшін Java коды 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 түйіндері арасындағы минималды қашықтыққа оңтайландырылған тәсіл 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), өйткені біз тек айнымалылардың тұрақты санын қолдандық. Ғарыштың күрделілігі тұрақты кеңістікке дейін азайды.