C++でKの葉を持つ二分木のすべてのノードを印刷します

この問題では、二分木と整数Kが与えられ、子サブツリーにKの葉を持つ二分木のすべてのノードを出力する必要があります。

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

リーフノード 二分木のは、ツリーの最後にあるノードです。

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

K =2

出力- {S}

この問題を解決するために、ツリーのトラバーサル（ポストオーダー）を実行します。ここで、葉の合計がKの場合、左側のサブツリーと右側のサブツリーがそれぞれ表示されます。現在のノードを出力します。 それ以外の場合は再帰的に呼び出し、サブツリーの葉がカウントされます。

このソリューションはトラバースに基づいているため、複雑さはツリーのサイズのオーダーになります。 時間計算量 − O（n）

例

上記のアプローチを実装するためのプログラム

#include<bits/stdc++.h>
using namespace std;
struct Node{
   char data ;
   struct Node * left, * right ;
};
struct Node * insertNode(char data){
   struct Node * node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int nodeWithKLeave(struct Node *ptr,int k){
   if (ptr == NULL)
      return 0;
   if (ptr->left == NULL && ptr->right == NULL)
      return 1;
   int total = nodeWithKLeave(ptr->left, k) + nodeWithKLeave(ptr->right, k);
   if (k == total)
      cout<<ptr->data<<" ";
   return total;
}
int main() {
   struct Node *root = insertNode('A');
   root->left = insertNode('B');
   root->right = insertNode('K');
   root->left->left = insertNode('N');
   root->left->right = insertNode('S');
   root->left->left->left = insertNode('X');
   root->left->left->right = insertNode('H');
   root->right->right = insertNode('E');
   root->right->left = insertNode('T');
   root->right->left->left = insertNode('O');
   root->right->left->right = insertNode('P');
   int K = 2;
   cout<<"Nodes with "<<K<<" leaves is :\n";
   nodeWithKLeave(root, K);
   return 0;
}

出力

Nodes with 2 leaves are:
N T