หาค่าสูงสุดระหว่างสองโหนดของ BST ใน C++

โจทย์

ได้รับอาร์เรย์ N องค์ประกอบ และจำนวนเต็มสองจำนวน A, B ซึ่งอยู่ในอาร์เรย์ที่ให้มา สร้าง Binary Search Tree โดยแทรกองค์ประกอบจาก arr[0] ถึง arr[n-1] งานคือหาองค์ประกอบสูงสุดในเส้นทางจาก A ไป B

ตัวอย่าง

ถ้าอาร์เรย์คือ {24, 23, 15, 36, 19, 41, 25, 35} เราสามารถสร้าง BST ได้ดังภาพ

ถ้าพิจารณา A = 19 และ B = 41 แล้วองค์ประกอบสูงสุดระหว่างสองโหนดนี้คือ 41

อัลกอริทึม

• หา Lowest Common Ancestor (LCA) ของโหนด A และ B
• หาโหนดสูงสุดระหว่าง LCA และ A เรียกว่า max1
• หาโหนดสูงสุดระหว่าง LCA และ B เรียกว่า max2
• คืนค่าสูงสุดของ max1 และ max2

ตัวอย่างโค้ด

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

struct node {
    int data;
    struct node* left;
    struct node* right;
};

node* createNode(int x) {
    node* p = new node();
    p->data = x;
    p->left = NULL;
    p->right = NULL;
    return p;
}

void insertNode(struct node* root, int x) {
    node* p = root, *q = NULL;
    while (p != NULL) {
        q = p;
        if (p->data < x) {
            p = p->right;
        } else {
            p = p->left;
        }
    }
    if (q == NULL) {
        p = createNode(x);
    } else {
        if (q->data < x) {
            q->right = createNode(x);
        } else {
            q->left = createNode(x);
        }
    }
}

int maxelpath(node* q, int x) {
    node* p = q;
    int mx = INT_MIN;
    while (p->data != x) {
        if (p->data > x) {
            mx = max(mx, p->data);
            p = p->left;
        } else {
            mx = max(mx, p->data);
            p = p->right;
        }
    }
    return max(mx, x);
}

int getMaximumElement(struct node* root, int x, int y) {
    node* p = root;
    while ((x < p->data && y < p->data) || (x > p->data && y > p->data)) {
        if (x < p->data && y < p->data) {
            p = p->left;
        } else if (x > p->data && y > p->data) {
            p = p->right;
        }
    }
    return max(maxelpath(p, x), maxelpath(p, y));
}

int main() {
    int arr[] = {24, 23, 15, 36, 19, 41, 25, 35};
    int a = 19, b = 41;
    int n = sizeof(arr) / sizeof(arr[0]);
    struct node* root = createNode(arr[0]);
    for (int i = 1; i < n; i++) insertNode(root, arr[i]);
    cout << "Maximum element = " << getMaximumElement(root, a, b) << endl;
    return 0;
}

ผลลัพธ์

Maximum element = 41