Đếm số phần tử nhỏ hơn gốc bằng duyệt Preorder của BST trong C++

Bạn được cho kết quả của duyệt preorder (tiền thứ tự) của một cây tìm kiếm nhị phân (BST). Nhiệm vụ là tìm số lượng phần tử nhỏ hơn gốc cây.

Phần tử đầu tiên trong mảng preorder chính là gốc của BST. Hãy xem ví dụ sau để hiểu rõ hơn.

Ví dụ

Đầu vào

preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]

Đầu ra

3

Có 3 phần tử nhỏ hơn gốc (gốc là 5): 4, 2, 1.

Thuật toán

• Khởi tạo mảng kết quả preorder.
• Lưu phần tử đầu tiên (gốc BST) vào biến root.
• Duyệt từ phần tử thứ 2 đến cuối mảng:
  • So sánh từng phần tử với root.
  • Nếu phần tử hiện tại nhỏ hơn root, tăng biến đếm.
• Trả về biến đếm.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

int getElementsCount(int arr[], int n) {
    if (n <= 0) return 0;
    int root = arr[0];
    int count = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i] < root) {
            count++;
        }
    }
    return count;
}

int main() {
    int preorder[] = {5, 4, 2, 1, 7, 6, 8, 9};
    int n = 8;
    cout << getElementsCount(preorder, n) << endl;
    return 0;
}

Kết quả

3