C++のバイナリツリーでルートから特定のノードまでの距離を検索します

これで、（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