이 문제에서 이진 트리와 정수 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