이 문제에서는 이진 트리가 제공되고 Q 쿼리가 제공됩니다. 우리의 임무는 바이너리 트리의 두 노드 사이의 거리를 찾기 위한 쿼리를 푸는 프로그램을 만드는 것입니다 – C++의 O(logn) 메서드입니다.
문제 설명
각 쿼리에서 이진 트리의 두 노드가 제공되고 두 노드 사이의 수 거리, 즉 다른 노드에서 한 노드에 도달하기 위해 횡단해야 하는 가장자리 수를 찾아야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력 :이진 트리
쿼리 =3
Q1 -> [2, 6]
Q2 -> [4, 1]
Q3 -> [5, 3]
출력: 3, 2, 3
솔루션 접근 방식
이 문제를 해결하기 위해 가장 낮은 공통 조상(LCA)과 그 거리를 사용하는 거리 공식을 사용할 것입니다.
거리(n1, n2) =거리(루트, n1) + 거리(루트, n1) - 2 * 거리(루트,LCA)
문제를 해결하려면 다음 단계를 따르십시오.
-
각 노드의 레벨, 즉 N1, N2, LCA를 찾으십시오.
-
그런 다음 Euler's Tourof 트리를 기반으로 이진 트리의 배열을 찾습니다.
-
그런 다음 LCA에 대한 세그먼트 트리를 생성합니다.
예시
#include <bits/stdc++.h>
#define MAX 1000
using namespace std;
int eulerArray[MAX];
int eIndex = 0;
int vis[MAX];
int L[MAX];
int H[MAX];
int level[MAX];
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data) {
struct Node* temp = new struct Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void FindNodeLevels(struct Node* root) {
if (!root)
return;
queue<pair<struct Node*, int> > q;
q.push({ root, 0 });
pair<struct Node*, int> p;
while (!q.empty()) {
p = q.front();
q.pop();
level[p.first->data] = p.second;
if (p.first->left)
q.push({ p.first->left, p.second + 1 });
if (p.first->right)
q.push({ p.first->right, p.second + 1 });
}
}
void createEulerTree(struct Node* root) {
eulerArray[++eIndex] = root->data;
if (root->left) {
createEulerTree(root->left);
eulerArray[++eIndex] = root->data;
}
if (root->right) {
createEulerTree(root->right);
eulerArray[++eIndex] = root->data;
}
}
void creareEulerArray(int size) {
for (int i = 1; i <= size; i++) {
L[i] = level[eulerArray[i]];
if (vis[eulerArray[i]] == 0) {
H[eulerArray[i]] = i;
vis[eulerArray[i]] = 1;
}
}
}
pair<int, int> seg[4 * MAX];
pair<int, int> min(pair<int, int> a, pair<int, int> b) {
if (a.first <= b.first)
return a;
else
return b;
}
pair<int, int> buildSegTree(int low, int high, int pos) {
if (low == high) {
seg[pos].first = L[low];
seg[pos].second = low;
return seg[pos];
}
int mid = low + (high - low) / 2;
buildSegTree(low, mid, 2 * pos);
buildSegTree(mid + 1, high, 2 * pos + 1);
seg[pos] = min(seg[2 * pos], seg[2 * pos + 1]);
}
pair<int, int> LCA(int qlow, int qhigh, int low, int high, int pos) {
if (qlow <= low && qhigh >= high)
return seg[pos];
if (qlow > high || qhigh < low)
return { INT_MAX, 0 };
int mid = low + (high - low) / 2;
return min(LCA(qlow, qhigh, low, mid, 2 * pos), LCA(qlow, qhigh,mid + 1, high, 2 * pos +1));
}
int CalcNodeDistance(int node1, int node2, int size) {
int prevn1 = node1, prevn2 = node2;
node1 = H[node1];
node2 = H[node2];
if (node2 < node1)
swap(node1, node2);
int lca = LCA(node1, node2, 1, size, 1).second;
lca = eulerArray[lca];
return level[prevn1] + level[prevn2] - 2 * level[lca];
}
int main() {
int N = 6;
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
FindNodeLevels(root);
createEulerTree(root);
creareEulerArray(2 * N - 1);
buildSegTree(1, 2 * N - 1, 1);
int Q = 4;
int query[Q][2] = {{1, 5}, {4, 6}, {3, 4}, {2, 4} };
for(int i = 0; i < Q; i++)
cout<<"The distance between two nodes of binary tree is "<<CalcNodeDistance(query[i][0], query[i][1], 2 * N - 1)<<endl;
return 0;
} 출력
The distance between two nodes of binary tree is 2 The distance between two nodes of binary tree is 4 The distance between two nodes of binary tree is 3 The distance between two nodes of binary tree is 1