home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Verify Preorder Sequence in Binary Search Tree ใน C++

สมมติว่ามีลำดับตัวเลข เราต้องตรวจสอบว่ามันเป็น preorder traversal sequence ที่ถูกต้องของ binary search tree หรือไม่ เราสามารถสมมติได้ว่าแต่ละตัวเลขในลำดับไม่ซ้ำกัน พิจารณา binary search tree ต่อไปนี้ −

Verify Preorder Sequence in Binary Search Tree ใน C++

เช่น ถ้าอินพุทเป็น [5,2,1,3,6] ผลลัพธ์จะเป็น true

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

  • itr := -1

  • low := -infinity

  • ลูป i := 0 ถึงขนาดของ preorder-1 ทำ −

    • x := preorder[i]

    • ถ้า x < low แล้ว −

      • คืนค่า false

    • ลูป while (itr >= 0 และ preorder[itr] < x) ทำ −

      • low := preorder[itr]

      • ลด itr ลง 1

    • เพิ่ม itr ขึ้น 1

    • preorder[itr] := x

  • คืนค่า true

ตัวอย่าง

ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −

#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}

เอาต์พุท

1