แทรกลงในโซลูชัน Leetcode แบบต้นไม้ค้นหาแบบไบนารี  


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน แอปเปิล Atlassian Facebook Google ไมโครซอฟท์
อัลกอริทึม ต้นไม้ค้นหาแบบไบนารี การเข้ารหัส สัมภาษณ์ สัมภาษณ์เตรียม LeetCode LeetCodeSolutions

ในปัญหานี้เราได้รับโหนดรูทของไฟล์ ต้นไม้ค้นหาแบบไบนารี ประกอบด้วยค่าจำนวนเต็มและค่าจำนวนเต็มของโหนดที่เราต้องเพิ่มใน 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 แบบต้นไม้ค้นหาแบบไบนารีหมุด

แนวทาง (ซ้ำ 

ในการตัดสินใจว่าควรแทรกโหนดใดในโครงสร้างการค้นหาแบบไบนารีของเราเราต้องตั้งค่าเส้นทางจากรูทไปยังโหนดที่เกี่ยวข้องซึ่งลูกทางซ้าย / ขวาจะเป็นโหนดที่กำหนด

เราสามารถแก้ปัญหานี้ซ้ำ ๆ ได้โดยส่งต่องานจากปัญหาไปสู่ปัญหาย่อย ในกรณีนี้การแทรกโหนดใหม่ลงในทรีหมายถึงการแทรกลงในทรีย่อยด้านซ้ายหรือทรีย่อยด้านขวา แนวคิดเดียวกันนี้ยังมีไว้สำหรับ subtrees อื่น ๆ อีกด้วย เราจำเป็นต้องตั้งค่ากรณีพื้นฐาน เมื่อเราไปถึงจุดที่รูทโหนดของทรีย่อยใด ๆ อยู่ NULLก็หมายความว่าเรามาถึงจุดสิ้นสุดของเส้นทางเพื่อแทรกโหนดเป้าหมาย ดังนั้นเราจึงส่งกลับไฟล์ ใหม่ ที่อยู่โหนดที่มีค่าโหนดเป็นค่าที่กำหนด ต้นไม้ค้นหาแบบไบนารีมีข้อได้เปรียบที่สำคัญในการค้นหาองค์ประกอบใด ๆ โดยพลการ O (logN) เวลาภายใต้กรณีเฉลี่ย ดังนั้นในกรณีนี้เราจะพบตำแหน่งของโหนดใหม่ที่จะแทรกในเวลาที่มีประสิทธิภาพ

ดูสิ่งนี้ด้วย
House Robber II โซลูชัน Leetcode

ขั้นตอนวิธี

  1. สร้างฟังก์ชัน insertIntoBST () ซึ่งส่งคืนที่อยู่ของไฟล์ ราก ของ BST หลังจากใส่ ปม
  2. insertIntoBST () มีสองพารามิเตอร์: ราก ของต้นไม้และ ความคุ้มค่า ของโหนดที่จะแทรก
  3. ฟังก์ชั่นจะทำสิ่งต่อไปนี้:
    • If ราก is โมฆะ ส่งคืนโหนดทรีใหม่ที่มีค่าเหมือนกับค่าที่กำหนด
    • หากค่าที่กำหนดคือ มากขึ้น กว่ามูลค่าของ ราก โหนดจากนั้นเรียกปัญหาเดียวกันไปยังทรีย่อยที่ถูกต้องแล้วส่งคืนรูท
      • รูทขวา = insertIntoBST (root-> ขวาค่า)
      • กลับ ราก
    • ค้นหาอื่นในทรีย่อยด้านซ้ายเป็น:
      • root.left= insertIntoBST (root.left ค่า)
      • กลับ ราก
  4. พิมพ์การส่งผ่านตามลำดับของทรีค้นหาแบบไบนารี

การใช้งานการแทรกลงในโซลูชัน 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;
    }
};

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

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 แบบต้นไม้ค้นหาแบบไบนารี

ความซับซ้อนของเวลา

O (H) = ความสูงของ BST = เข้าสู่ระบบN (โดยที่ N = จำนวนโหนดใน BST) ในกรณีโดยเฉลี่ย (ขณะที่เราทำการเรียก logN แบบเรียกซ้ำ) แต่ บน) ในกรณีที่เลวร้ายที่สุดเมื่อต้นไม้เบ้ เนื่องจากในกรณีที่ต้นไม้เอียงการค้นหาจะกลายเป็นไฟล์ เชิงเส้น หนึ่ง.

ดูสิ่งนี้ด้วย
เพิ่ม Binary Leetcode Solution

ความซับซ้อนของพื้นที่

O (H) โดยเฉลี่ยแล้ว บน) ในกรณีที่เลวร้ายที่สุด กรณีที่มี Space Complexity เหมือนกับ Time Complexity ตรงนี้เนื่องจากขึ้นอยู่กับจำนวนการเรียกซ้ำที่เราทำ

แนวทาง (ที่กล่าวย้ำ 

เราสามารถทำตามแนวทางข้างต้นซ้ำ ๆ เพื่อปรับปรุงความซับซ้อนของพื้นที่ การเรียกซ้ำใช้สแต็กเฟรมซึ่งใช้หน่วยความจำ ดังนั้นในการแก้ปัญหาซ้ำเราจึงป้องกันไม่ให้ไฟล์ โหลดการโทรซ้ำ และไปตามต้นไม้บนเส้นทางการค้นหาของเราจนกว่าเราจะชนโหนดที่มีทั้งซ้ายหรือขวา NULL. เมื่อเรามี root.left / root.right = NULL, เราตั้งค่าโหนดนี้ให้เท่ากับโหนดใหม่ที่มีค่าเดียวกับค่าที่กำหนด โปรดทราบว่าเราตัดสินใจเลือกเส้นทางโดยการเปรียบเทียบค่ากับ ราก มูลค่าในการเรียกซ้ำทุกครั้ง

ขั้นตอนวิธี

  1. เรามีไฟล์ insertIntoBST () เพื่อวัตถุประสงค์เดียวกันกับข้างต้น
  2. ถ้า ราก เป็นโมฆะ
    1. ส่งคืนโหนดใหม่ที่มีค่าเหมือนกับค่าที่กำหนด
  3. สร้างสำเนาของรูทพูด ตัวแทนเชิด เพื่อจัดการเนื้อหาของ BST
  4. ในขณะที่ ตัวแทนเชิด is ไม่ NULL
    1. หากค่าที่กำหนดมากกว่า root.val
      1. If รูทขวา เป็นโมฆะ
        1. รูทขวา = โหนดใหม่ที่มีค่าที่กำหนด
        2. กลับ ราก
      2. อื่นตั้ง
        1. ราก = รูทขวาเพื่อข้ามไปยังทรีย่อยด้านขวา
    2. หากค่าน้อยกว่าหรือเท่ากับ root.val
      1. ถ้า root.left เป็นโมฆะ
        1. root.left = โหนดใหม่ที่มีค่าที่กำหนด
        2. กลับ ราก
      2. อื่นตั้ง
        1. ราก = root.leftเพื่อข้ามไปยังทรีย่อยด้านซ้าย
  5. พิมพ์ Inorder traversal ของ BST

การใช้งานการแทรกลงในโซลูชัน 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;
    }
};

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

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 แบบต้นไม้ค้นหาแบบไบนารี

ความซับซ้อนของเวลา

O (H) = ความสูงของ BST = เข้าสู่ระบบN (โดยที่ N = จำนวนโหนดใน BST) ในกรณีเฉลี่ย แต่ บน) ในกรณีที่เลวร้ายที่สุดเมื่อต้นไม้เบ้ อีกครั้งความซับซ้อนของเวลาขึ้นอยู่กับจำนวนการทำซ้ำที่เราทำเพื่อไปถึงปลายทางหลังจากนั้นควรแทรกโหนดที่กำหนดและขึ้นอยู่กับโครงสร้างของต้นไม้

ดูสิ่งนี้ด้วย
มุมมองด้านบนของ Binary Tree

ความซับซ้อนของพื้นที่

O (1). แม้ในกรณีที่เลวร้ายที่สุดเราใช้พื้นที่คงที่สำหรับตัวแปรเท่านั้น