تحقق مما إذا كانت كل عقدة داخلية في BST لها طفل واحد بالضبط  


مستوى الصعوبة سهل
كثيرا ما يطلب في اكسنتشر أمازون حلول مونوتايب Paypal سينوبسيس
شجرة البحث الثنائية شجرة ثنائية شجرة

المشكلة بيان  

تنص مشكلة "تحقق مما إذا كانت كل عقدة داخلية في BST تحتوي على عنصر فرعي واحد بالضبط" على أنه تم منحك اجتياز الطلب المسبق لشجرة بحث ثنائية. وتحتاج إلى معرفة ما إذا كانت جميع العقد غير الورقية تحتوي على طفل واحد فقط. هنا نعتبر أيضًا أن جميع العقد في الإدخال المحدد لها قيم مميزة.

مثال  

تحقق مما إذا كانت كل عقدة داخلية في BST لها طفل واحد بالضبط

 

Preorder Traversal: 6 15 7 9 11
Yes

التفسير: كما نرى في الصورة أعلاه ، فإن الشجرة ذات اجتياز الطلب المسبق المحدد لها طفل واحد لكل عقدة داخلية. وبالتالي فإن الناتج هو نعم.

نهج للتحقق مما إذا كانت كل عقدة داخلية في BST لها عنصر واحد بالضبط  

اجتياز الطلب المسبق يعني أنه تم إعطاء الأفضلية للجذر وطباعته قبل الشجرة الفرعية اليمنى واليسرى. وبالتالي فإن العناصر بعد الجذر تكون إما أصغر أو أكبر من الجذر. لذا ، إذا احتجنا إلى التحقق مما إذا كان تسلسل معين هو طلب مسبق لـ a شجرة البحث الثنائية. يمكننا استخدام حلقتين متداخلتين للتحقق مما إذا كان بإمكاننا إنشاء شجرة بحث ثنائية بالتسلسل المحدد.

نهج ساذج

كما ناقشنا بالفعل ، يحتوي اجتياز الطلب المسبق على الجذر في الجزء العلوي وبعد طباعة الشجرة الفرعية اليمنى واليسرى. الآن تم الانتهاء من هذه العملية متكرر حتى يتم تغطية جميع العقد في الشجرة. لذلك ، يمكننا التحقق مما إذا كان التسلسل المعطى يمثل BST ، نقوم بتشغيل حلقتين متداخلتين حيث يتم استخدام الحلقة الخارجية لاختيار جذر. وتتحقق الحلقة المتداخلة مما إذا كانت العناصر التي تليها يمكن أن تمثل الشجرة الفرعية اليمنى واليسرى. لذلك ، نتحقق مما إذا كانت جميع العناصر أقل من العنصر المختار حتى فهرس معين. والعناصر بعد ذلك أكبر من العنصر المختار. الآن ، يمكننا تعديل هذا النهج وفقًا لحالة الاستخدام الخاصة بنا.

انظر أيضا
تحويل BST عادي إلى BST متوازن

دعونا نرى كيف يمكننا تعديل الخوارزمية للتحقق مما إذا كانت كل عقدة داخلية في BST لها طفل واحد بالضبط. إذا كان الطفل الداخلي لـ BST لديه طفل واحد بالضبط. هذا يعني أن كل عقدة داخلية يمكن أن يكون لها إما شجرة فرعية يسرى أو شجرة فرعية على اليمين. لن يحتوي على كلتا الشجرتين الفرعيتين في نفس الوقت. وبالتالي ، لتلخيص خوارزمية لدينا. نستخدم حلقتين متداخلتين ، حيث تختار الحلقة الخارجية عنصرًا. ثم يتم استخدام الحلقة المتداخلة للتحقق مما إذا كانت العناصر التي تليها تنتمي إلى أي من الأشجار الفرعية. في السابق ، اعتدنا أن يكون لدينا فهرس معين كانت العناصر قبله أقل من الجذر ، وبعد ذلك كانت العناصر أكبر منه. الآن ، لن نجد أي فهرس من هذا القبيل. لكن هذه الطريقة ليست فعالة بما يكفي لأنها تحتوي على تعقيد كثير الحدود الزمني لـ O (N ^ 2).

نهج فعال

حتى الآن ، أوضحنا نقطة واحدة مفادها أن جميع العناصر الفرعية لأي عقدة ستكون إما أصغر أو أكبر من العقدة الحالية وفقًا لهذه المشكلة. لذلك ، للتحقق مما إذا كانت كل عقدة داخلية في BST لها طفل واحد بالضبط ، نجد التالي التالي للطلب المسبق للعقدة الحالية. ثم نجد آخر طلب مسبق خلف للعقدة الحالية. إذا كان كلاهما أقل من العقدة الحالية أو أكبر من العقدة الحالية. ثم ننتقل بعد ذلك إلى علمنا أن العقدة الحالية بها شجرتان فرعيتان يسار ويمين لأن أحد العناصر أصغر من العقدة الحالية. وعقدة أخرى أكبر من العقدة الحالية. وبالتالي نعيد القيمة false أو -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 لتخزين تسلسل الطلب المسبق.