Bạn được cung cấp kết quả của quá trình duyệt đặt hàng trước. Bạn cần tìm số phần tử nhỏ hơn phần tử gốc.
Phần tử đầu tiên trong trình duyệt đặt hàng trước là phần tử gốc của BST. Hãy xem một ví dụ.
Đầu vào
preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]
Đầu ra
3
Có ba phần tử nhỏ hơn gốc. Gốc là 5.
Thuật toán
-
Khởi tạo kết quả đặt hàng trước trong một mảng.
-
Lưu trữ phần tử đầu tiên, tức là gốc của BST trong một biến.
-
Viết một vòng lặp lặp lại từ phần tử thứ 2 của kết quả đặt hàng trước.
-
So sánh mọi phần tử với gốc.
-
Nếu phần tử hiện tại lớn hơn phần tử gốc, thì hãy tăng số lượng.
-
-
Trả lại số đếm.
Thực hiện
Sau đây là cách thực hiện thuật toán trên trong 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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
3