BST Leetcode шешіміндегі минималды абсолютті айырмашылық


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

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

BST Leetcode шешіміндегі минималды абсолютті айырмашылық

1

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

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

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

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