ตรวจสอบว่าแต่ละโหนดภายในของ BST มีลูกเดียวหรือไม่  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคเซนเจอร์ อเมซอน โซลูชั่นโมโนไทป์ บัตรเครดิต/เดบิต หรือ PayPal Synopsys
ต้นไม้ค้นหาแบบไบนารี ต้นไม้ไบนารี ต้นไม้

คำชี้แจงปัญหา  

“ ตรวจสอบว่าแต่ละโหนดภายในของ BST มีลูกเดียวหรือไม่” ปัญหาระบุว่าคุณได้รับการสั่งซื้อล่วงหน้าของโครงสร้างการค้นหาแบบไบนารี และคุณต้องหาว่าโหนดที่ไม่ใช่ลีฟทั้งหมดมีลูกคนเดียวหรือไม่ นอกจากนี้เรายังพิจารณาด้วยว่าโหนดทั้งหมดในอินพุตที่ระบุมีค่าที่แตกต่างกัน

ตัวอย่าง  

ตรวจสอบว่าแต่ละโหนดภายในของ BST มีลูกเดียวหรือไม่

 

Preorder Traversal: 6 15 7 9 11
Yes

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

วิธีการตรวจสอบว่าแต่ละโหนดภายในของ BST มีลูกเดียวหรือไม่  

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

แนวทางที่ไร้เดียงสา

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

ดูสิ่งนี้ด้วย
แปลง BST ปกติเป็น BST สมดุล

มาดูกันว่าเราจะแก้ไขอัลกอริทึมเพื่อตรวจสอบได้อย่างไรว่าแต่ละโหนดภายในของ BST มีลูกเดียวหรือไม่ หากลูกภายในของ BST มีลูกเดียว ซึ่งหมายความว่าแต่ละโหนดภายในสามารถมีทรีย่อยด้านซ้ายหรือทรีย่อยด้านขวา จะไม่มีทั้งสอง subtrees ในเวลาเดียวกัน ดังนั้นเพื่อสรุปอัลกอริทึมของเรา เราใช้สองลูปซ้อนกันโดยที่วงนอกเลือกองค์ประกอบ จากนั้นใช้ลูปที่ซ้อนกันเพื่อตรวจสอบว่าองค์ประกอบที่ตามมาเป็นของใครของต้นไม้ย่อย ก่อนหน้านี้เราเคยมีดัชนีหนึ่งมาก่อนว่าองค์ประกอบใดน้อยกว่ารูทหลังจากนั้นองค์ประกอบมีค่ามากกว่ามัน ตอนนี้เราจะไม่พบดัชนีดังกล่าว แต่วิธีนี้ไม่มีประสิทธิภาพเพียงพอเนื่องจากมีความซับซ้อนของเวลาพหุนามของ O (N ^ 2)

แนวทางที่มีประสิทธิภาพ

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

ดูสิ่งนี้ด้วย
จำนวนขั้นต่ำขององค์ประกอบที่แตกต่างกันหลังจากลบรายการ m

รหัส  

รหัส C ++ เพื่อตรวจสอบว่าแต่ละโหนดภายในของ BST มีลูกเดียวหรือไม่

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

bool checkIfALlInternalNodesHaveSingleChild(vector<int> preorder, int i){
    int n = preorder.size();
    if(i==n-1)return true;
    int next = preorder[i+1] - preorder[i];
    int lst = preorder[n-1] - preorder[i];
    int prod = next*lst;
    if(prod<0)
    return false;
    return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
}

int main()
{
    int n;cin>>n;
    vector<int> preorder(n);
    for(int i=0;i<n;i++)cin>>preorder[i];
    cout<<(checkIfALlInternalNodesHaveSingleChild(preorder, 0) ? "Yes" : "No");
}
5
6 15 7 9 11
Yes

รหัส Java เพื่อตรวจสอบว่าแต่ละโหนดภายในของ BST มีลูกเดียวหรือไม่

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
  static boolean checkIfALlInternalNodesHaveSingleChild(int preorder[], int i){
      int n = preorder.length;
      if(i==n-1)return true;
      int next = preorder[i+1] - preorder[i];
      int lst = preorder[n-1] - preorder[i];
      int prod = next*lst;
      if(prod<0)
      return false;
      return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int preorder[] = new int[n];
      for(int i=0;i<n;i++)preorder[i] = sc.nextInt();
      boolean answer = checkIfALlInternalNodesHaveSingleChild(preorder, 0);
      System.out.print(answer == true ? "Yes" : "No");
  }
}
5
6 15 7 9 11
Yes

การวิเคราะห์ความซับซ้อน  

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

O (N) เนื่องจากเราเพิ่งข้ามผ่านอาร์เรย์การสั่งซื้อล่วงหน้า และอาร์เรย์การสั่งซื้อล่วงหน้ามีองค์ประกอบ N ดังนั้นจึงมีความซับซ้อนของเวลาเชิงเส้น

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

O (N) พื้นที่ที่ต้องการสำหรับสแต็กแบบเรียกซ้ำและเรายังใช้อาร์เรย์อินพุตขนาด N เพื่อจัดเก็บลำดับการสั่งซื้อล่วงหน้า