Ҷустуҷӯ дар ҳалли дутарафаи дарахти Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад себ IBM
Дарахти ҷустуҷӯи бинарӣ

Дар ин мушкилот, ба мо а Дарахти ҷустуҷӯи бинарӣ ва як адад. Мо бояд суроғаи гиреҳро бо арзиши бутуни додашуда яксон ёбем. Ҳамчун чек, мо бояд гардиши пешакии зердарахтро, ки ин гиреҳро ҳамчун реша дорад, чоп кунем. Агар дар дарахт арзиши ба бутуни додашуда баробар набошад, мо бояд баргардем ночиз, яъне дарахти холӣ.

мисол

     2
    
  /     \

1         3

             \

               4


Target Value = 3
3 4
     5

  /      \

1         10 


Target Value = 4
Empty BST

Шарҳи №1

BST гиреҳро бо арзиши 3 дар бар мегирад, бинобар ин мо зердарахти онро бармегардонем ва гардиши пешакии онро чоп мекунем.

Шарҳи №2

BST ягон гиреҳ бо арзиши 4 надорад, бинобар ин мо NULL-ро бармегардонем ва "Empty BST" -ро чоп мекунем.

Равиш (рекурсивӣ)

Биёед дар бораи он фикр кунем, ки чӣ гуна мушкилот дар ин ҳолат аз зерпроблема вобаста аст. Биёед бигӯем, ки функсияи мо суроғаи гиреҳро бо арзиши ҳадаф бармегардонад, агар пайдо шавад. Мо аз решаи дарахт сар мекунем. Агар ин гиреҳ бошад НУЛ, равшан аст, ки мо ба дарахти ҷустуҷӯи дуӣ расидем ва аз ин рӯ ягон гиреҳ бо арзиши ҳадаф вуҷуд надорад. Ҳамин тавр, мо бармегардем НОЛЛ. Ба ҳамин монанд, мо арзиши гиреҳ ба арзиши ҳадаф баробарем, мо ин гиреҳро бармегардонем. Дар акси ҳол, мо медонем, ки гиреҳи ҳадафманд дар ё хоҳад буд чап дарахт ё рост subtree решаи ҳозира. Мо метавонем самтро (чап ё рост) тавассути муқоисаи root.value ва арзиши ҳадаф муайян кунем. Ҳамин тавр, мо ҳамон функсияи рекурсивиро бо реша as решаи чап or реша. рост.

Ҷустуҷӯ дар ҳалли дутарафаи дарахти Leetcode

Алгоритм

  1. Функсия эҷод кунед searchBST () баргардонидани суроғаи мақсаднок
  2. If реша баробар аст ночиз OR реша бо арзиши ҳадаф баробар аст:
    • Решаро баргардонед
  3. Агар root.value аз арзиши ҳадаф бузургтар бошад:
    1. бозгашт searchBST (root.left, val)
  4. бозгашт searchBST (root.right, val)
  5. Гузариши пешакии гиреҳи ҳадафро чоп кунед

Амалисозии Ҷустуҷӯ дар Solution Leetcode Tree Binary Search Tree

Барномаи C ++

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

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

void preorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    return;
}

BSTNode* searchBST(BSTNode* root , int val)
{
    if(root == NULL)
        return root;
    if(val == root->value)
        return root;
    if(val < root->value)
        return searchBST(root->left , val);
    return searchBST(root->right , val);
}

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

Барномаи Java

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

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        if(root == null)
            return root;
        if(val == root.value)
            return root;
        if(val < root.value)
            return searchBST(root.left , val);
        return searchBST(root.right , val);
    }

    static void preorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        System.out.print(root.value + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return;
    }
}
3 4

Таҳлили мураккабии ҷустуҷӯ дар ҳалли дутарафаи дарахти ҷустуҷӯ дар Leetcode

Мураккабии вақт

O (H), H = logN = Баландии BST дар ҳолатҳои миёна ва О (Н), Н = андозаи BST дар ҳолатҳои бадтарин. Мо дарахтро як маротиба дар бадтарин ҳолате мегузарем, ки ҳангоми BST дар каҷ шудан ба амал ояд.

Мураккабии фазо

О (Н) дар ҳолатҳои миёна, вақте ки мо зангҳои рекурсивиро истифода бурда, ҳар як гиреҳро убур мекунем. О (Н) дар бадтарин ҳолат. Як чизи муҳим он аст, ки баъзе тартибдиҳандагон имкон медиҳанд думи-рекурсия ва дар он ҳолатҳо, мураккабии фазо мегардад О (1).

Равиш (такрорӣ)

Монанди усули дар боло овардашуда, мо метавонем ба зери дарахти чап ё рост ҷаҳем, агар қимати ҳадаф дар гиреҳи мавҷуда мавҷуд набошад, мо метавонем онро бо такрори такрорӣ иҷро кунем root = root.left or root = root.right дар ҳар такрор то реша пайдо шуданаш бекор. Агар мо фаҳмем, ки арзиши реша ба арзиши ҳадаф дар ҳама гуна такрор такрор мешавад, он решаро бармегардонем. Дар акси ҳол, мо бармегардем бекор.

Алгоритм

  1. Функсияи шабеҳро эҷод кунед searchBST () ки суроғаи гиреҳи ҳадафро бар мегардонад
  2. ҳол он реша is не бекор:
    • if арзиш ба арзиши ҳадаф баробар аст
      • бозгашт реша
    • if root.val is бештар аз арзиши мақсаднок
      • Ба зери дарахти рост ҳаракат кунед ба тариқи: root = root.right
    • боз
      • Ба зердарахт ба тарафи чап ҳаракат кунед: root = root.left
  3. бозгашт ночиз
  4. Гузариши пешакии гиреҳи ҳадафро чоп кунед

Амалисозии Ҷустуҷӯ дар Solution Leetcode Tree Binary Search Tree

Барномаи C ++

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

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

void preorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    return;
}

BSTNode* searchBST(BSTNode* root , int val)
{
    while(root != NULL)
    {
        if(root->value == val)
            return root;
        if(root->value > val)
            root = root->left;
        else
            root = root->right;
    }
    return NULL;
}

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

Барномаи Java

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

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        while(root != null)
        {
            if(root.value == val)
                return root;
            if(root.value > val)
                root = root.left;
            else
                root = root.right;
        }
        return null;
    }

    static void preorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        System.out.print(root.value + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return;
    }
}
3 4

Таҳлили мураккабии ҷустуҷӯ дар ҳалли дутарафаи дарахти ҷустуҷӯ дар Leetcode

Мураккабии вақт

O (H = logN) дар ҳолатҳои миёна ва О (Н) дар ҳолатҳои бадтарин (BST-и каҷшуда), ҳамон тавре ки усули дар боло зикршуда.

Мураккабии фазо

О (1) чунон ки мо танҳо фазои хотираи доимиро истифода мебарем.