C++の二分木で最も近い葉を見つけます

1つの二分木が与えられたとします。さまざまなレベルのリーフノードがあります。ノードを指す別のポインターが与えられます。尖ったノードから最も近いリーフノードまでの距離を見つける必要があります。ツリーが以下のようであると考えてください-

ここで、リーフノードは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