【C++】部分木にK個の葉を持つ二分木のノードをすべて出力するアルゴリズム

問題概要

この問題では、二分木と整数Kが与えられ、「自分の部分木（子孫ノード）の中にちょうどK個の葉を持つ」ノードをすべて見つけて出力することが求められます。

二分木とは、各ノードが持てる子ノードの数が最大2個（0個・1個・2個）である特別な木構造のことです。

葉ノードとは、二分木において子を一切持たない、木の末端に位置するノードのことです。

具体例で理解する

次のような二分木を考えてみましょう。

            A
          /   \
         B     K
        / \   / \
       N   S T   E
      / \   / \
     X   H O   P

ここで K = 2 とした場合、出力：{N, T} となります。

• ノードNの部分木には葉XとHの2つがあるため該当
• ノードTの部分木には葉OとPの2つがあるため該当
• その他のノードは部分木内の葉の数が2ではないため対象外

解法のアプローチ

この問題は、木を後順走査（postorder traversal）することで効率的に解けます。各ノードに対して左部分木と右部分木それぞれの葉の数を再帰的にカウントし、その合計がKと一致していれば現在のノードを出力します。一致しない場合は、合計値をそのまま親ノードへ返して処理を続けます。

アルゴリズムの手順を整理すると次のようになります。

1. ノードがNULLなら0を返す
2. ノードが葉ノード（左右どちらも子を持たない）なら1を返す
3. 左部分木と右部分木の葉の数を再帰的に取得し、合計を計算する
4. 合計がKと等しければ、そのノードのデータを出力する
5. 合計値を呼び出し元に返す

この解法は木全体を一度だけ走査するため、計算量は木のサイズに比例します。
時間計算量： 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

期待どおり、部分木に2つの葉を持つノード「N」と「T」が出力されました。