ตรวจสอบลำดับการสั่งซื้อล่วงหน้าในแผนผังการค้นหาแบบไบนารีใน C++

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

ดังนั้นหากอินพุตเป็น [5,2,1,3,6] ผลลัพธ์จะเป็นจริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

itr :=-1
ต่ำ :=-อินฟินิตี้
สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของการสั่งซื้อล่วงหน้า ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -
- x :=สั่งซื้อล่วงหน้า[i]
- ถ้า x <ต่ำ แล้ว −
  - คืนค่าเท็จ
- ในขณะที่ (itr>=0 และสั่งซื้อล่วงหน้า[itr]
  - ต่ำ :=สั่งซื้อล่วงหน้า[itr]
  - (ลดลงทีละ 1)
- (เพิ่มขึ้นอีก 1)
- สั่งซื้อล่วงหน้า[itr] :=x
คืนความจริง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool verifyPreorder(vector<int<& preorder) {
      int itr = -1;
      int low = INT_MIN;
      for (int i = 0; i < preorder.size(); i++) {
         int x = preorder[i];
         if (x < low)
            return false;
         while (itr >= 0 && preorder[itr] < x) {
            low = preorder[itr];
            itr--;
         }
         itr++;
         preorder[itr] = x;
      }
      return true;
   }
};
main(){
   Solution ob;
   vector<int< v = {5,2,1,3,6};
   cout << (ob.verifyPreorder(v));
}

อินพุต

{5,2,1,3,6}