C++의 이진 트리에서 가장 가까운 잎 찾기

하나의 이진 트리가 제공된다고 가정합니다. 다른 수준의 리프 노드가 있습니다. 노드를 가리키는 또 다른 포인터가 제공됩니다. 뾰족한 노드에서 가장 가까운 잎 노드까지의 거리를 찾아야 합니다. 트리가 아래와 같다고 생각해보세요 -

여기서 리프 노드는 2, -2 및 6입니다. 포인터가 노드 -5를 가리키는 경우 -5에서 가장 가까운 노드는 거리 1에 있습니다.

이 문제를 해결하기 위해 우리는 주어진 노드에 뿌리를 둔 하위 트리를 탐색하고 하위 트리에서 가장 가까운 잎을 찾은 다음 거리를 저장합니다. 이제 루트에서 시작하여 트리를 탐색합니다. 노드 x가 왼쪽 하위 트리에 있으면 오른쪽 하위 트리를 검색하고 그 반대도 마찬가지입니다.

예시

#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;
}
void getLeafDownward(Node *root, int level, int *minDist) {
   if (root == NULL)
      return ;
   if (root->left == NULL && root->right == NULL) {
      if (level < (*minDist))
         *minDist = level;
      return;
   }
   getLeafDownward(root->left, level+1, minDist);
   getLeafDownward(root->right, level+1, minDist);
}
int getFromParent(Node * root, Node *x, int *minDist) {
   if (root == NULL)
      return -1;
   if (root == x)
      return 0;
   int l = getFromParent(root->left, x, minDist);
   if (l != -1) {
      getLeafDownward(root->right, l+2, minDist);
      return l+1;
   }
   int r = getFromParent(root->right, x, minDist);
   if (r != -1) {
      getLeafDownward(root->left, r+2, minDist);
      return r+1;
   }
   return -1;
}
int minimumDistance(Node *root, Node *x) {
   int minDist = INT8_MAX;
   getLeafDownward(x, 0, &minDist);
   getFromParent(root, x, &minDist);
   return minDist;
}
int main() {
   Node* root = getNode(4);
   root->left = getNode(2);
   root->right = getNode(-5);
   root->right->left = getNode(-2);
   root->right->right = getNode(6);
   Node *x = root->right;
   cout << "Closest distance of leaf from " << x->data <<" is: " << minimumDistance(root, x);
}

출력

Closest distance of leaf from -5 is: 1