C++에서 BST의 두 노드 사이의 최대 요소

문제 설명

N 요소의 배열과 주어진 배열에 속하는 두 개의 정수 A, B가 주어집니다. arr[0]에서 arr[n-1]까지 요소를 삽입하여 이진 검색 트리를 만듭니다. 작업은 A에서 B로의 경로에서 최대 요소를 찾는 것입니다.

예시

배열이 {24, 23, 15, 36, 19, 41, 25, 35}인 경우 다음과 같이 BST를 구성할 수 있습니다. -

A =19 및 B =41을 고려하면 이 두 노드 사이의 최대 요소는 41입니다.

알고리즘

• 노드 A와 B의 최하위 공통 조상(LCA) 찾기
• 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