Сұрыпталған массивті екілік іздеу ағашының Leetcode шешіміне түрлендіру


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Airbnb Amazon алма Bloomberg Cisco Google Microsoft Oracle Spotify VMware Yahoo
Екілік іздеу ағашы Тереңдікті бірінші іздеу

Қарастырайық, бізге сұрыпталған массив бүтін сандар. Мақсат осы массивтен ағаш биіктігі теңдестірілген етіп екілік іздеу ағашын құру. Егер ағаштағы кез-келген түйіннің сол және оң жақ кіші ағаштарының биіктік айырмашылығы ең көбі 1 болса, онда биіктік теңдестірілген деп аталады.

Бірнеше шешім болуы мүмкін екенін табу оңай. Біз кез-келген дұрыс шешімді табуымыз керек. Бұл мәселеде бізге ағашты басып шығарудың қажеті жоқ, бірақ оны жасау керек. Біз оның алдын-ала өтуін басып шығаруымыз керек.

мысал

Array = {-4 , 0 , 1 , 2 , 7}
1 -4 0 2 7

Түсіндіру: БСТ:

Сұрыпталған массивті екілік іздеу ағашының Leetcode шешіміне түрлендіру

 

Array = {1 , 2 , 3}
2 1 3

Түсіндіру: БСТ:

Сұрыпталған массивті екілік іздеу ағашының Leetcode шешіміне түрлендіру

Тәсіл (Рекурсия)

Біз екі нәрсені қадағалап отыруымыз керек:

  1. Кез-келген түйінде сол жақтағы балалар сияқты кіші элементтер болуы керек, ал керісінше оң жақтағы балалар үшін
  2. BST биіктікте теңдестірілген болуы керек

Ағашты кез-келген сәтте теңгерімді ұстап тұру үшін біз массивтің ортаңғы элементін түбір ретінде таңдауымыз керек. Осылайша, бізде биіктік айырмасы болады 1 егер массивтің өлшемі тең және биіктік айырмасы болса, сол және оң жақ кіші ағаштар арасында массив коэффициентті болған кезде.

Енді кез-келген орта түйінді түбір ретінде таңдағанда, сол жақ ішкі тармақтан сол жақ ішкі ағашты, оң жақ ішкі аралықтан оң жақ кіші ағашты құруымыз керек. Бұл біздің бастапқы проблемамыздың ішкі проблемасы, сондықтан біз оны рекурсивті түрде шеше аламыз. Ортаңғы түйінге сол және оң жақ қосалқы ағашты тағайындағаннан кейін, біз оны қайтара аламыз және екілік іздеу ағашының постеректорлық траверциясын басып шығара аламыз.

Алгоритм

  1. Басқа функция жасаңыз convertArrayToBST () ол берілген массивтің кез-келген нақты диапазонын түрлендіреді және оған сәйкес BST түбірлік түйінін қайтарады.
  2. L = массивтің сол жақ шегі және R = массивтің жоғарыда көрсетілген шегі болсын.
    1. Егер L> R
      • қайтару NULL, өйткені біз қате ауқымды аламыз
    2. Егер L == R
      • мәні бар жаңа түйінді қайтарыңыз Массив [L] 
    3. Осы диапазонның орта түйінін келесідей табыңыз орта = (L + (R - L) / 2)
      • Мәні бірдей жаңа BST түйіні ретінде бастаңыз Массив [орта]
      • Берілсін сол және оң сол функциялар сияқты ішкі ағаштар сәйкесінше сол және оң жақ ішкі ауқымдарға шақырылады
      • Басты қайтарыңыз
  3. Екілік іздеу ағашының алдын-ала өтуін басып шығарыңыз

Сұрыпталған массивті екілік іздеу ағашына арналған Leetcode шешіміне түрлендіруді жүзеге асыру

Сұрыпталған массивті екілік іздеу ағашына айналдыру үшін C ++ шешімі

#include <bits/stdc++.h>
using namespace std;

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

BSTNode* convertArrayToBST(vector <int> &a , int l , int r)
{
    if(l > r)
        return NULL;
    if(l == r)
        return new BSTNode(a[l]);
    int mid = (l + (r - l) / 2);
    BSTNode* head = new BSTNode(a[mid]);
    head->left = convertArrayToBST(a , l , mid - 1);
    head->right = convertArrayToBST(a , mid + 1 , r);
    return head;
}

BSTNode* sortedArrayToBST(vector<int>& a)
{
    int n = a.size();
    return convertArrayToBST(a , 0 , n - 1);
}

void preorder(BSTNode* head)
{
    if(!head)
        return;
    cout << head->value << " ";
    preorder(head->left);
    preorder(head->right);
}


int main()
{
    vector <int> a = {-4 , 0 , 1 , 2 , 7};
    BSTNode* head = sortedArrayToBST(a);
    preorder(head);
    return 0;
}

Сұрыпталған массивті екілік іздеу ағашына айналдыру үшін Java шешімі

class BSTNode
{
    int value;
    BSTNode left , right;
    BSTNode(int x)
    {
        value = x;
        left = null;
        right = null;
    }
}

class convert_array_to_BST
{
    public static void main(String args[])
    {
        int[] a = {-4 , 0 , 1 , 2 , 7};
        BSTNode head = sortedArrayToBST(a);
        preorder(head);
    }

    static BSTNode convertArrayToBST(int[] a , int l , int r)
    {
        if(l > r)
            return null;
        if(l == r)
            return new BSTNode(a[l]);
        int mid = (l + (r - l) / 2);
        BSTNode head = new BSTNode(a[mid]);
        head.left = convertArrayToBST(a , l , mid - 1);
        head.right = convertArrayToBST(a , mid + 1 , r);
        return head;
    }

    static BSTNode sortedArrayToBST(int[] a)
    {
        return convertArrayToBST(a , 0 , a.length - 1);
    }

    static void preorder(BSTNode head)
    {
        if(head == null)
            return;
        System.out.print(head.value + " ");
        preorder(head.left);
        preorder(head.right);
    }
}
1 -4 0 2 7

Сұрыпталған массивті екілік іздеу ағашына түрлендірудің күрделілігін талдау

Уақыттың күрделілігі

O (N), N = ағаштағы элементтер саны. БСТ құру және алдын-ала өтпелі жолды басып шығару үшін біз барлық элементтерге барамыз.

Ғарыштың күрделілігі

O (H), мұндағы H = ағаштың биіктігі = logN. Екі рекурсивті функцияларда да біз ағаштың биіктікте екендігіне көз жеткіземіз, сондықтан максимумды қолданамыз O (H) рекурсивті стек жақтауларына арналған орын.