ໃສ່ເຂົ້າໃນວິທີແກ້ບັນຫາຕົ້ນໄມ້ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ Atlassian ເຟສບຸກ ກູໂກ Microsoft
ຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບການໃຫ້ຮາກຂອງ a ຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ ບັນຈຸຄຸນຄ່າຂອງເລກເຕັມແລະຄ່າຂອງຕົວເລກທີ່ພວກເຮົາຕ້ອງຕື່ມໃສ່ໃນ Binary Search Tree ແລະສົ່ງຄືນໂຄງສ້າງຂອງມັນ. ຫລັງຈາກໃສ່ອົງປະກອບເຂົ້າໃນ BST, ພວກເຮົາຕ້ອງໄດ້ພິມ Inorder Traversal ຂອງມັນ.

ຍົກຕົວຢ່າງ

Binary Search Tree:
 
    7
 
  /     \

3         10

        /

      8
Integer Value = 11
3 7 8 10 11
Binary Search Tree:
           5

         /

       4

     /

   3
Integer Value = 2
2 3 4 5

ຄໍາອະທິບາຍ

ໃສ່ເຂົ້າໃນວິທີແກ້ບັນຫາຕົ້ນໄມ້ Leetcode

ໃສ່ເຂົ້າໃນວິທີແກ້ບັນຫາຕົ້ນໄມ້ Leetcode

ວິທີການ (ປະກົດຕົວ)

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

ພວກເຮົາສາມາດແກ້ໄຂບັນຫານີ້ໂດຍການສົ່ງຕໍ່ວຽກຈາກບັນຫາໄປສູ່ບັນຫາຍ່ອຍຂອງມັນ. ໃນກໍລະນີນີ້, ການໃສ່ node ໃໝ່ ເຂົ້າໄປໃນຕົ້ນໄມ້ ໝາຍ ເຖິງການເອົາມັນລົງໄປໃນບົດບັນຍັດເບື້ອງຊ້າຍຫລືເບື້ອງຊ້າຍ. ແນວຄວາມຄິດດຽວກັນນີ້ຍັງຖືເອົາ ສຳ ລັບບົດບັນຍັດໃດ ໜຶ່ງ ຕໍ່ໄປ. ພວກເຮົາຕ້ອງ ກຳ ນົດຄະດີພື້ນຖານ. ໃນເວລາທີ່ພວກເຮົາໄປເຖິງຈຸດທີ່ຮາກຂໍ້ຂອງຂໍ້ຍ່ອຍຕ່າງໆແມ່ນ NULL, ມັນຈະຫມາຍຄວາມວ່າພວກເຮົາໄດ້ໄປຮອດຈຸດສຸດທ້າຍຂອງເສັ້ນທາງເພື່ອໃສ່ node ເປົ້າ ໝາຍ. ດັ່ງນັ້ນ, ພວກເຮົາສົ່ງຄືນ a ໃຫມ່ node address ມີຄ່າ node ເປັນຄ່າທີ່ໃຫ້ໄວ້. ຕົ້ນໄມ້ຄົ້ນຫາຖານສອງມີປະໂຫຍດທີ່ ສຳ ຄັນໃນການຄົ້ນຫາອົງປະກອບໃດ ໜຶ່ງ ທີ່ຕົນເອງມັກ O (logN) ທີ່ໃຊ້ເວລາພາຍໃຕ້ກໍລະນີສະເລ່ຍ. ດັ່ງນັ້ນ, ໃນກໍລະນີນີ້, ພວກເຮົາຊອກຫາ ຕຳ ແໜ່ງ ຂອງໂຫນດ ໃໝ່ ທີ່ຈະຖືກໃສ່ໃນເວລາທີ່ມີປະສິດຕິພາບ

ລະບົບວິເຄາະ

  1. ສ້າງ ໜ້າ ທີ່ insertIntoBST () ເຊິ່ງສົ່ງຄືນທີ່ຢູ່ຂອງ ຮາກ ຂອງ BST ຫຼັງຈາກໃສ່ສິ່ງທີ່ໄດ້ຮັບ node
  2. insertIntoBST () ມີສອງຕົວ ກຳ ນົດ: ຮາກ ຂອງຕົ້ນໄມ້ແລະ ມູນຄ່າ ຂອງຂໍ້ທີ່ຈະຖືກໃສ່ລົງ
  3. ໜ້າ ທີ່ຈະເຮັດດັ່ງຕໍ່ໄປນີ້:
    • If ຮາກ is NULL, ກັບຄືນຂໍ້ຂອງຕົ້ນໄມ້ ໃໝ່ ທີ່ມີຄ່າເທົ່າກັບຄ່າທີ່ໄດ້ໃຫ້ໄວ້
    • ຖ້າວ່າມູນຄ່າທີ່ໃຫ້ໄວ້ແມ່ນ ຫຼາຍກວ່າ ກ່ວາມູນຄ່າຂອງ ຮາກ node, ຫຼັງຈາກນັ້ນໃຫ້ໂທຫາບັນຫາດຽວກັນກັບລັດຖະບັນຍັດຂວາແລະຈາກນັ້ນສົ່ງຮາກຄືນ
      • root.right = insertIntoBST (ຮາກ -> ຖືກ, ຄຸນຄ່າ)
      • ການກັບຄືນມາ ຮາກ
    • ຄົ້ນຫາໃນບົດບັນຍັດຊ້າຍດັ່ງລຸ່ມນີ້:
      • root.left= insertIntoBST (root.left, ມູນຄ່າ)
      • ການກັບຄືນມາ ຮາກ
  4. ພິມເຄື່ອງ ໝາຍ ການຄ້າທີ່ບໍ່ເປັນທາງການຂອງຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ

ການຈັດຕັ້ງປະຕິບັດຂອງການໃສ່ເຂົ້າໃນການຄົ້ນຫາຖານສອງແບບ Leetcode Solution

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

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


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

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

Java Program

class BSTNode
{
    int value;
    BSTNode left , right;

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

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        if(val > root.value)
        {
            root.right = insertIntoBST(root.right , val);
            return root;
        }
        root.left = insertIntoBST(root.left , val);
        return root;
    }

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

3 7 8 10 11

ການວິເຄາະທີ່ສັບສົນຂອງການໃສ່ເຂົ້າໃນການຄົ້ນຫາແບບສອງຕົວຂອງ Leetcode Solution

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

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

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

O (H) ໃນກໍລະນີສະເລ່ຍ. ໂອ (N) ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ. ກໍລະນີຂອງ Space Complexity ແມ່ນຄືກັນກັບ Time Complexity ຢູ່ທີ່ນີ້ຍ້ອນວ່າມັນຂື້ນກັບ ຈຳ ນວນການໂທຫາທີ່ເອີ້ນຄືນ.

ວິທີການ (Iterative)

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

ລະບົບວິເຄາະ

  1. ພວກເຮົາອີກເທື່ອຫນຶ່ງມີ insertIntoBST () ສຳ ລັບຈຸດປະສົງດຽວກັນກັບຂ້າງເທິງ
  2. ຖ້າ ຮາກ ແມ່ນ NULL
    1. ກັບຄືນ node ໃຫມ່ທີ່ມີມູນຄ່າເທົ່າກັບມູນຄ່າທີ່ໄດ້ຮັບ
  3. ສ້າງ ສຳ ເນົາຮາກ, ເວົ້າ dummy ໝູນ ໃຊ້ເນື້ອໃນຂອງ BST
  4. ໃນຂະນະທີ່ dummy is ບໍ່ NULL
    1. ຖ້າມີມູນຄ່າຫຼາຍກ່ວາ root.val
      1. If root.right ແມ່ນ NULL
        1. root.right = ຂໍ້ ໃໝ່ ທີ່ມີຄ່າໃຫ້
        2. ການກັບຄືນມາ ຮາກ
      2. ອື່ນ, ທີ່ກໍານົດໄວ້
        1. ຮາກ = root.right, ເພື່ອເຕັ້ນໄປຫາ subtree ຂວາ
    2. ອື່ນຖ້າວ່າມູນຄ່າຕໍ່າກວ່າຫຼືເທົ່າກັບ root.val
      1. ຖ້າ root.left ແມ່ນ NULL
        1. root.left = ຂໍ້ ໃໝ່ ທີ່ມີຄ່າໃຫ້
        2. ການກັບຄືນມາ ຮາກ
      2. ອື່ນ, ທີ່ກໍານົດໄວ້
        1. ຮາກ = root.left, ເພື່ອເຕັ້ນໄປຫາ subtree ຊ້າຍ
  5. ພິມເສັ້ນທາງຜ່ານທາງອິນເຕີເນັດຂອງ BST

ການຈັດຕັ້ງປະຕິບັດຂອງການໃສ່ເຂົ້າໃນການຄົ້ນຫາຖານສອງແບບ Leetcode Solution

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

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

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

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

Java Program

class BSTNode
{
    int value;
    BSTNode left , right;

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

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

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

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

3 7 8 10 11

ການວິເຄາະທີ່ສັບສົນຂອງການໃສ່ເຂົ້າໃນການຄົ້ນຫາແບບສອງຕົວຂອງ Leetcode Solution

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

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

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

O (1). ເຖິງແມ່ນວ່າໃນກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດ, ພວກເຮົາພຽງແຕ່ໃຊ້ພື້ນທີ່ຄົງທີ່ ສຳ ລັບຕົວແປຕ່າງໆ.