二分木の2つのノード間の距離を見つけるためのクエリ– C ++のO（logn）メソッド

この問題では、二分木が与えられ、Qクエリが与えられます。私たちのタスクは、クエリを解決してバイナリツリーの2つのノード間の距離を見つけるプログラムを作成することです– C ++のO（logn）メソッド。

問題の説明

各クエリでは、バイナリツリーの2つのノードが与えられ、2つのノード間の距離、つまり、別のノードから1つのノードに到達するために通過するエッジの数を見つける必要があります。

問題を理解するために例を見てみましょう

入力 ：二分木

クエリ=3

Q1-> [2、6]

Q2-> [4、1]

Q3-> [5、3]

出力： 3、2、3

ソリューションアプローチ

この問題を解決するために、最も低い共通祖先（LCA）を使用する距離式とその距離を使用します。

Distance（n1、n2）=distance（root、n1）+ distance（root、n1）-2 * distance（root、LCA）

問題を解決するには、次の手順に従います。

• 各ノードのレベル（N1、N2、LCA）を見つけます。

• 次に、オイラーのツリーのツアーに基づいた二分木の配列を見つけます。

• 次に、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