C++로 이진 트리에서 K개의 리프 노드를 가진 모든 노드 출력하기

이 문제에서는 하나의 이진 트리(binary tree)와 정수 K가 주어지며, 자식 서브트리(subtree)에 정확히 K개의 리프(잎) 노드를 가진 모든 노드를 찾아 출력해야 합니다.

핵심 개념 정리

이진 트리는 각 노드가 최대 두 개의 자식 노드(0~2개)만 가질 수 있는 특수한 형태의 트리입니다.

리프 노드(leaf node)는 트리의 맨 끝에 위치하며 자식 노드가 없는 노드를 의미합니다.

예시를 통해 문제를 구체적으로 살펴보겠습니다.

K = 2

출력 결과 − {S}

문제 해결 접근 방법

이 문제는 후위 순회(postorder traversal) 방식으로 트리를 탐색하여 해결할 수 있습니다. 각 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리의 리프 노드 수를 재귀적으로 계산하고, 그 합이 K와 같다면 현재 노드를 출력합니다. 조건을 만족하지 않으면 하위 서브트리의 리프 개수를 그대로 상위 호출로 반환하여 누적합니다.

이 방법은 트리의 모든 노드를 한 번씩만 방문하므로, 시간 복잡도는 트리의 크기에 비례합니다.

시간 복잡도 − O(n), 여기서 n은 트리의 전체 노드 수입니다.

예제 코드

위 접근 방식을 구현한 C++ 프로그램입니다.

#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

위 실행 결과에서 노드 N은 자식 노드 X와 H 두 개의 리프를 가지고 있고, 노드 T 역시 자식 노드 O와 P 두 개의 리프를 가지고 있으므로 두 노드가 출력됩니다.