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