C++で特定のノードから距離kにあるすべてのノードを出力します

この問題では、二分木、ターゲットノード、整数Kが与えられます。ターゲットノードから距離Kにあるツリーのすべてのノードを印刷する必要があります。 。

二分木 は、各ノードに最大2つのノード（1つまたは2つ/なし）を持つ特別なツリーです。

問題を理解するために例を見てみましょう

K =2

ターゲットノード：9

出力 −

5 1 3.

説明 −

距離は、ノードの上位、下位、または同じレベルで取得できます。したがって、それに応じてノードを返します。

この問題を解決するには、ターゲットノードからK距離離れたノードのタイプを理解する必要があります。

上記の試験から、k個の離れたノードがターゲットノードのサブツリー（5と1）にあるか、ターゲットノードの祖先のサブツリーのどこかにあることがわかります（3）。

ここで、最初のケースの解決策を見つける方法は、ターゲットノードのサブツリーをトラバースし、ターゲットからのノードの距離がKであるかどうかを確認することです。そうであれば、ノードを出力します。

2番目のケースでは、ターゲットの祖先ノードとこれらの祖先のサブツリーをチェックし、ターゲットから距離Kですべてを印刷する必要があります。

以下のプログラムは、私たちのソリューションの実装を示しています-

例

#include <iostream>
using namespace std;
struct node {
   int data;
   struct node *left, *right;
};
void printSubtreeNodes(node *root, int k) {
   if (root == NULL || k < 0) return;
   if (k==0){
      cout<<root->data<<"\t";
      return;
   }
   printSubtreeNodes(root->left, k-1);
   printSubtreeNodes(root->right, k-1);
}
int printKNodes(node* root, node* target , int k){
   if (root == NULL) return -1;
   if (root == target){
      printSubtreeNodes(root, k);
      return 0;
   }
   int dl = printKNodes(root->left, target, k);
   if (dl != -1){
      if (dl + 1 == k)
         cout<<root->data<<"\t";
      else
         printSubtreeNodes(root->right, k-dl-2);
      return 1 + dl;
   }
   int dr = printKNodes(root->right, target, k);
      if (dr != -1){
         if (dr + 1 == k)
            cout << root->data << endl;
         else
            printSubtreeNodes(root->left, k-dr-2);
         return 1 + dr;
      }
      return -1;
   }
   node *insertNode(int data){
      node *temp = new node;
      temp->data = data;
      temp->left = temp->right = NULL;
      return temp;      
}
int main(){
   node * root = insertNode(6);
   root->left = insertNode(3);
   root->right = insertNode(9);
   root->left->right = insertNode(4);
   root->right->left = insertNode(8);
   root->right->right = insertNode(10);
   root->right->right->left = insertNode(5);
   root->right->right->right = insertNode(1);
   node * target = root->right;
   int K = 2;
   cout<<"Nodes at distance "<<K<<" from the target node are :\n";
   printKNodes(root, target, K);
   return 0;
}

Nodes at distance 2 from the target n tode are − 
5 1 3