ຄົ້ນຫາໃນຖານຂໍ້ມູນ Leetcode Solution ຂອງ Binary Search Tree


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ຈາກຫນາກແອບເປີ IBM
ຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບກ ຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ ແລະເລກເຕັມ. ພວກເຮົາຕ້ອງຊອກຫາທີ່ຢູ່ຂອງ Node ທີ່ມີຄ່າເທົ່າກັບເລກເຕັມທີ່ໃຫ້. ໃນຖານະເປັນການກວດກາ, ພວກເຮົາ ຈຳ ເປັນຕ້ອງໄດ້ພິມ preversvers ຂອງຕົ້ນໄມ້ຍ່ອຍທີ່ມີ node ນີ້ເປັນຮາກ. ຖ້າວ່າມັນບໍ່ມີຄ່າເທົ່າກັບຕົວເລກທີ່ໃຫ້ຢູ່ໃນຕົ້ນໄມ້, ພວກເຮົາ ຈຳ ເປັນຕ້ອງກັບຄືນມາ NULL, ie, ຕົ້ນໄມ້ທີ່ເປົ່າຫວ່າງ.

ຍົກຕົວຢ່າງ

     2
    
  /     \

1         3

             \

               4


Target Value = 3
3 4
     5

  /      \

1         10 


Target Value = 4
Empty BST

ຄຳ ອະທິບາຍ # 1

BST ປະກອບດ້ວຍຂໍ້ທີ່ມີຄ່າ 3, ດັ່ງນັ້ນພວກເຮົາສົ່ງຕົ້ນໄມ້ຍ່ອຍຂອງມັນແລະພິມຮູບການປ່ຽນແປງກ່ອນ ກຳ ນົດ.

ຄຳ ອະທິບາຍ # 2

BST ບໍ່ມີ node ທີ່ມີຄ່າ 4, ດັ່ງນັ້ນພວກເຮົາສົ່ງ NULL ແລະພິມ“ BST ເປົ່າ”.

ວິທີການ (Recursive)

ໃຫ້ພວກເຮົາຄິດວ່າບັນຫາແມ່ນຂື້ນກັບໂຄງການຍ່ອຍໃນກໍລະນີນີ້. ໃຫ້ເວົ້າວ່າຫນ້າທີ່ຂອງພວກເຮົາສົ່ງຄືນທີ່ຢູ່ຂອງ Node ດ້ວຍມູນຄ່າເປົ້າ ໝາຍ, ຖ້າພົບ. ພວກເຮົາເລີ່ມຕົ້ນຈາກຮາກຂອງຕົ້ນໄມ້. ຖ້າ node ນີ້ແມ່ນ NULL, ມັນເປັນທີ່ຈະແຈ້ງວ່າພວກເຮົາໄດ້ເຖິງຈຸດສຸດທ້າຍຂອງຕົ້ນໄມ້ຄົ້ນຫາຖານສອງແລະເພາະສະນັ້ນຈຶ່ງບໍ່ມີຂໍ້ມູນທີ່ມີມູນຄ່າເປົ້າ ໝາຍ. ດັ່ງນັ້ນ, ພວກເຮົາກັບຄືນມາ NULL. ເຊັ່ນດຽວກັນ, ພວກເຮົາຄ່າ node ແມ່ນເທົ່າກັບມູນຄ່າເປົ້າ ໝາຍ, ພວກເຮົາສົ່ງຄືນ node ນີ້. ຖ້າບໍ່ດັ່ງນັ້ນ, ພວກເຮົາຮູ້ວ່າຂໍ້ມູນທີ່ຖືກເປົ້າ ໝາຍ ຈະຢູ່ໃນ ໄວ້ ລັດຖະມົນຕີຫຼື ສິດ subtree ຂອງຮາກໃນປະຈຸບັນ. ພວກເຮົາສາມາດຕັດສິນໃຈທິດທາງ (ຊ້າຍຫລືຂວາ) ໂດຍການປຽບທຽບຄ່າ root.value ແລະມູນຄ່າເປົ້າ ໝາຍ. ສະນັ້ນ, ພວກເຮົາເອີ້ນວ່າຟັງຊັນເອີ້ນຫາດຽວກັນກັບ ຮາກ as root.left or root.right.

ຄົ້ນຫາໃນຖານຂໍ້ມູນ Leetcode Solution ຂອງ Binary Search Tree

ລະບົບວິເຄາະ

  1. ສ້າງ ໜ້າ ທີ່ searchBST () ເພື່ອກັບຄືນທີ່ຢູ່ເປົ້າ ໝາຍ
  2. If ຮາກ ເທົ່າກັບ null OR ຮາກ ມີຄຸນຄ່າເທົ່າກັບເປົ້າ ໝາຍ ດັ່ງກ່າວ:
    • ກັບຄືນຮາກ
  3. ຖ້າ root.value ໃຫຍ່ກວ່າມູນຄ່າເປົ້າ ໝາຍ:
    1. ການກັບຄືນມາ searchBST (root.left, val)
  4. Return searchBST (root.right, val)
  5. ພິມເສັ້ນທາງຜ່ານເປົ້າ ໝາຍ ທີ່ ກຳ ນົດໄວ້

ການຈັດຕັ້ງປະຕິບັດການຄົ້ນຫາໃນຖານຂໍ້ມູນການຄົ້ນຫາຖານສອງແບບ Leetcode

ໂຄງການ 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 Program

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 Tree Tree Bolution

ຄວາມສັບສົນເວລາ

O (H), H = logN = ຄວາມສູງຂອງ BST ໃນກໍລະນີສະເລ່ຍແລະ O (N), ນ = ຂະ ໜາດ ຂອງ BST ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ. ພວກເຮົາຂ້າມຕົ້ນໄມ້ຄັ້ງ ໜຶ່ງ ໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດເຊິ່ງເກີດຂື້ນເມື່ອ BST ສະສົມ.

ຄວາມສັບສົນໃນອະວະກາດ

O (H) ໃນກໍລະນີສະເລ່ຍໃນຂະນະທີ່ພວກເຮົາໃຊ້ການໂທຫາເພື່ອເອີ້ນຄືນທຸກໆເສັ້ນ. ໂອ (N) ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ. ໝາຍ ເຫດ ສຳ ຄັນ ໜຶ່ງ ແມ່ນບາງເຄື່ອງລວບລວມໃຊ້ໄດ້ ການຮຽກຄືນຫາງ ແລະໃນກໍລະນີເຫຼົ່ານັ້ນ, ຄວາມສັບສົນຂອງພື້ນທີ່ກາຍເປັນ O (1).

ວິທີການ (ຄິດໄລ່)

ຄ້າຍຄືກັບວິທີການຂ້າງເທິງນີ້, ພວກເຮົາສາມາດໂດດໄປຫາລັດຖະບັນຍັດຊ້າຍຫລືຂວາຖ້າຫາກວ່າມູນຄ່າເປົ້າ ໝາຍ ບໍ່ຢູ່ໃນ node ປັດຈຸບັນ, ພວກເຮົາສາມາດເຮັດມັນໄດ້ໂດຍການມອບ ໝາຍ ຮາກ = root.left or ຮາກ = root.right ໃນເວລາທຸກຈົນກ່ວາຮາກຈະກາຍເປັນ null. ຖ້າພວກເຮົາເຫັນວ່າຄຸນຄ່າຂອງຮາກເທົ່າກັບມູນຄ່າເປົ້າ ໝາຍ ໃນເວລາໃດກໍ່ຕາມ, ພວກເຮົາກັບຄືນຮາກນັ້ນ. ຖ້າບໍ່ດັ່ງນັ້ນ, ພວກເຮົາກັບຄືນມາ null.

ລະບົບວິເຄາະ

  1. ສ້າງ ໜ້າ ທີ່ຄ້າຍຄືກັນ searchBST () ທີ່ກັບທີ່ຢູ່ຂອງຂໍ້ມູນເປົ້າ ໝາຍ
  2. ໃນຂະນະທີ່ ຮາກ is ບໍ່ ບໍ່ມີ:
    • if root.value ເທົ່າກັບມູນຄ່າເປົ້າ ໝາຍ
      • ການກັບຄືນມາ ຮາກ
    • if root.val is ຫຼາຍກວ່າ ກ່ວາມູນຄ່າເປົ້າ ໝາຍ
      • ຍ້າຍໄປຢູ່ໃນລັດຖະບັນຍັດຂວາເປັນ: ຮາກ = root.right
    • ອື່ນ
      • ຍ້າຍໄປຢູ່ໃນລັດຖະບັນຍັດເບື້ອງຊ້າຍເປັນ: ຮາກ = root.left
  3. Return null
  4. ພິມເສັ້ນທາງຜ່ານເປົ້າ ໝາຍ ທີ່ ກຳ ນົດໄວ້

ການຈັດຕັ້ງປະຕິບັດການຄົ້ນຫາໃນຖານຂໍ້ມູນການຄົ້ນຫາຖານສອງແບບ Leetcode

ໂຄງການ 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 Program

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 Tree Tree Bolution

ຄວາມສັບສົນເວລາ

O (H = logN) ໃນກໍລະນີສະເລ່ຍແລະ ໂອ (N) ໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດ (ມີຄວາມສົງໄສ BST), ຄືກັນກັບວິທີການຂ້າງເທິງ.

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ດັ່ງທີ່ພວກເຮົາໃຊ້ພຽງແຕ່ພື້ນທີ່ ໜ່ວຍ ຄວາມ ຈຳ ເທົ່ານັ້ນ