C++ 프로그램에서 이진 트리의 두 노드 사이의 거리 찾기

이 문제에서는 이진 트리와 두 개의 노드가 제공됩니다. 우리의 임무는 이진 트리의 두 노드 사이의 거리를 찾는 프로그램을 만드는 것입니다.

문제 설명

한 노드에서 다른 노드로 이동할 때 가로지르는 최소 모서리 수인 두 노드 사이의 거리를 찾아야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 :이진 트리

노드1 =3, 노드2 =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