จำนวนองค์ประกอบที่น้อยกว่ารากโดยใช้การท่องลำดับก่อนรากของ BST ใน C++

โจทย์

คุณได้รับผลลัพธ์ของการท่องลำดับก่อนราก (preorder traversal) ของต้นไม้ค้นหาทวีพจน์ (BST) คุณต้องหาจำนวนองค์ประกอบที่น้อยกว่าราก (root)

องค์ประกอบแรกในลำดับก่อนรากคือรากของ 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; 
}

ผลลัพธ์

หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้