แปลงอาร์เรย์ที่เรียงลำดับเป็นโซลูชัน Leetcode ต้นไม้ค้นหาแบบไบนารี


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี Airbnb อเมซอน แอปเปิล บลูมเบิร์ก ซิสโก้ Google ไมโครซอฟท์ คำพยากรณ์ Spotify VMware yahoo
ต้นไม้ค้นหาแบบไบนารี การค้นหาครั้งแรกเชิงลึก

พิจารณาว่าเราได้รับการจัดเรียง แถว จำนวนเต็ม เป้าหมายคือการสร้าง Binary Search Tree จากอาร์เรย์นี้เพื่อให้ต้นไม้มีความสมดุลของความสูง โปรดทราบว่าต้นไม้ถูกกำหนดให้มีความสมดุลของความสูงหากความแตกต่างของความสูงของต้นไม้ย่อยด้านซ้ายและด้านขวาของโหนดใด ๆ ในต้นไม้มีค่ามากที่สุด 1

เป็นเรื่องง่ายที่จะพบว่าสามารถมีวิธีแก้ปัญหาได้หลายวิธี เราต้องหาวิธีแก้ปัญหาที่ถูกต้อง โปรดทราบว่าในปัญหานี้เราไม่จำเป็นต้องพิมพ์ต้นไม้ แต่ต้องสร้างขึ้นมาใหม่ เราจำเป็นต้องพิมพ์การส่งผ่านคำสั่งซื้อล่วงหน้า

ตัวอย่าง

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

คำอธิบาย: BST คือ:

แปลงอาร์เรย์ที่เรียงลำดับเป็นโซลูชัน Leetcode ต้นไม้ค้นหาแบบไบนารี

 

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

คำอธิบาย: BST คือ:

แปลงอาร์เรย์ที่เรียงลำดับเป็นโซลูชัน Leetcode ต้นไม้ค้นหาแบบไบนารี

แนวทาง (Recursion)

เราต้องติดตามสองสิ่ง:

  1. โหนดใด ๆ ควรมีองค์ประกอบที่เล็กกว่าเป็นลูกทางซ้ายและในทางกลับกันสำหรับลูกด้านขวา
  2. BST ควรมีความสูงสมดุล

เพื่อให้ต้นไม้มีความสมดุลในทุกขณะเราต้องเลือกองค์ประกอบกลางของอาร์เรย์เป็นราก ด้วยวิธีนี้เราจะมีความสูงต่างกัน 1 ระหว่างต้นไม้ย่อยด้านซ้ายและด้านขวาหากอาร์เรย์มีขนาดเท่ากันและมีความสูงแตกต่างกัน เมื่ออาร์เรย์มีขนาดต่อรอง

ตอนนี้เมื่อเราเลือกโหนดกลางใด ๆ เป็นรูทเราจะต้องสร้างทรีย่อยด้านซ้ายจาก subarray ด้านซ้ายและทรีย่อยด้านขวาจาก subarray ด้านขวา นี่เป็นปัญหาย่อยของปัญหาเดิมของเราและด้วยเหตุนี้เราจึงสามารถแก้ปัญหาซ้ำได้ หลังจากกำหนดทรีย่อยซ้ายและขวาให้กับโหนดกลางแล้วเราสามารถส่งคืนและพิมพ์การข้ามผ่านของลำดับท้ายของ Binary Search Tree

ขั้นตอนวิธี

  1. สร้างฟังก์ชันอื่น ConverArrayToBST () ซึ่งจะแปลงช่วงเฉพาะของอาร์เรย์ที่กำหนดและส่งคืนโหนดรูท BST ที่เกี่ยวข้อง
  2. ให้ L = ขีด จำกัด ด้านซ้ายของอาร์เรย์และ R = ขีด จำกัด ด้านขวาของอาร์เรย์ในช่วงดังกล่าวข้างต้น
    1. ถ้า L> R
      • กลับ NULLเนื่องจากเราได้รับช่วงที่ไม่ถูกต้อง
    2. ถ้า L == R
      • ส่งคืนโหนดใหม่ที่มีค่าเหมือนกับ อาร์เรย์ [L] 
    3. ค้นหาโหนดกลางของช่วงนี้เป็น กลาง = (L + (R - L) / 2)
      • เริ่มต้นส่วนหัวเป็น BST Node ใหม่ด้วยค่าเดียวกับ อาร์เรย์ [กลาง]
      • กำหนด ซ้าย และ ขวา ต้นไม้ย่อยเป็นฟังก์ชันเดียวกันที่เรียกในช่วงย่อยด้านซ้ายและด้านขวาตามลำดับ
      • กลับหัว
  3. พิมพ์การส่งผ่านคำสั่งซื้อล่วงหน้าของ Binary Search Tree

การใช้งานการแปลงอาร์เรย์ที่เรียงลำดับเป็นไบนารี Search Tree 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;
    }
};

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 Solution เพื่อแปลงเรียงลำดับ Array เป็น Binary Search Tree

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

การวิเคราะห์ความซับซ้อนของการแปลงอาร์เรย์ที่เรียงลำดับเป็นโซลูชัน Leetcode ต้นไม้ค้นหาแบบไบนารี

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

บน), N = จำนวนองค์ประกอบในต้นไม้ เราเยี่ยมชมทุกองค์ประกอบเพื่อสร้าง BST และพิมพ์การส่งผ่านคำสั่งซื้อล่วงหน้า

ความซับซ้อนของอวกาศ

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