C++プログラムで二分木の2つのノード間の距離を見つける

この問題では、二分木と2つのノードが与えられます。私たちの仕事は、二分木の2つのノード間の距離を見つけるプログラムを作成することです。

問題の説明

2つのノード間の距離を見つける必要があります。これは、あるノードから別のノードに移動するときに通過するエッジの最小数です。

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

入力 ：二分木

Node1 =3、Node2 =5

出力 ：3

説明

ノード3からノード5へのパスは3->1->2->5です。距離3を作る3つのエッジが通過します。

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

この問題の簡単な解決策は、特定のノードに最も低い共通の祖先ノードを使用してから、次の式を適用することです。

distance（node1、node2）=distance（root、node1）+ distance（root、node2）+ distance（root、LCA）

例

#include <iostream>
using namespace std;
struct Node{
   struct Node *left, *right;
   int key;
};
Node* insertNode(int key){
   Node *temp = new Node;
   temp->key = key;
   temp->left = temp->right = NULL;
   return temp;
}
int calcNodeLevel(Node *root, int val, int level) {
   if (root == NULL)
      return -1;
   if (root->key == val)
      return level;
   int lvl = calcNodeLevel(root->left, val, level+1);
   return (lvl != -1)? lvl : calcNodeLevel(root->right, val, level+1);
}
Node *findDistanceRec(Node* root, int node1, int node2, int &dist1, int &dist2, int &dist, int lvl){
   if (root == NULL) return NULL;
   if (root->key == node1){
      dist1 = lvl;
      return root;
   }
   if (root->key == node2){
      dist2 = lvl;
      return root;
   }
   Node *leftLCA = findDistanceRec(root->left, node1, node2, dist1,dist2, dist, lvl+1);
   Node *rightLCA = findDistanceRec(root->right, node1, node2, dist1,dist2, dist, lvl+1);
   if (leftLCA && rightLCA){
      dist = dist1 + dist2 - 2*lvl;
      return root;
   }
   return (leftLCA != NULL)? leftLCA: rightLCA;
}
int CalcNodeDistance(Node *root, int node1, int node2) {
   int dist1 = -1, dist2 = -1, dist;
   Node *lca = findDistanceRec(root, node1, node2, dist1, dist2, dist, 1);
   if (dist1 != -1 && dist2 != -1)
      return dist;
   if (dist1 != -1){
      dist = calcNodeLevel(lca, node2, 0);
      return dist;
   }
   if (dist2 != -1){
      dist = calcNodeLevel(lca, node1, 0);
      return dist;
   }
   return -1;
}
int main(){
   Node * root = insertNode(1);
   root->left = insertNode(2);
   root->right = insertNode(3);
   root->left->left = insertNode(4);
   root->left->right = insertNode(5);
   root->right->left = insertNode(6);
   cout<<"Distance between node with value 5 and node with value 3 is"<<CalcNodeDistance(root, 3, 5);
   return 0;
}

出力

Distance between node with value 5 and node with value 3 is 3