C++의 이진 트리에서 루트에서 주어진 노드까지의 거리 찾기

노드가 거의 없는 이진 트리가 있다고 가정해 보겠습니다. 루트와 다른 노드 u 사이의 거리를 찾아야 합니다. 트리가 아래와 같다고 가정:

이제 (root, 6) =2 사이의 거리, 경로 길이는 2, (root, 8) =3 사이의 거리 등

이 문제를 해결하기 위해 재귀적 접근 방식을 사용하여 왼쪽 및 오른쪽 하위 트리에서 노드를 검색하고 각 레벨의 길이도 업데이트합니다.

예

#include<iostream>
using namespace std;
class Node {
   public:
      int data;
   Node *left, *right;
};
Node* getNode(int data) {
   Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return node;
}
int getDistance(Node *root, int x) {
   if (root == NULL)
      return -1;
   int dist = -1;
   if ((root->data == x) || (dist = getDistance(root->left, x)) >= 0 || (dist = getDistance(root->right, x)) >= 0)
      return dist + 1;
   return dist;
}
int main() {
   Node* root = getNode(1);
   root->left = getNode(2);
   root->right = getNode(3);
   root->left->left = getNode(4);
   root->left->right = getNode(5);
   root->right->left = getNode(6);
   root->right->right = getNode(7);
   root->right->left->right = getNode(8);
   cout <<"Distance from root to node 6 is: " << getDistance(root,6);
   cout << "\nDistance from root to node 8 is: " << getDistance(root,8);
}

출력

Distance from root to node 6 is: 2
Distance from root to node 8 is: 3