คุณจะได้รับผลลัพธ์ของการสั่งจองล่วงหน้า คุณต้องหาจำนวนองค์ประกอบที่น้อยกว่ารูท
องค์ประกอบแรกในการข้ามผ่านของการสั่งซื้อล่วงหน้าคือรูทของ BST มาดูตัวอย่างกัน
ป้อนข้อมูล
preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]
ผลผลิต
3
มีสามองค์ประกอบที่น้อยกว่ารูท รากคือ 5.
อัลกอริทึม
-
เริ่มต้นผลการสั่งซื้อล่วงหน้าในอาร์เรย์
-
เก็บองค์ประกอบแรก เช่น รูทของ BST ไว้ในตัวแปร
-
เขียนลูปที่วนซ้ำจากองค์ประกอบที่ 2 ของผลลัพธ์การสั่งซื้อล่วงหน้า
-
เปรียบเทียบทุกองค์ประกอบด้วยรูท
-
หากองค์ประกอบปัจจุบันมากกว่ารูท ให้เพิ่มจำนวนขึ้น
-
-
คืนค่าการนับ
การนำไปใช้
ต่อไปนี้เป็นการนำอัลกอริธึมข้างต้นไปใช้ใน C++
#include <bits/stdc++.h>
using namespace std;
int getElementsCount(int arr[], int n) {
if (n < 0) {
return 0;
}
int i, root = arr[0], count = 0;
for(i = 1; i < n; i++) {
if(arr[i] < root) {
count += 1;
}
}
return count;
}
int main() {
int preorder[] = {5, 4, 2, 1, 7, 6, 8, 9};
int n = 8;
cout << getElementsCount(preorder, n) << endl;
return 0;
} ผลลัพธ์
หากคุณเรียกใช้โค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้
3
