C++で長さがK未満のルートからリーフへのパス上のノードを削除する方法

問題の概要

木構造が与えられたとき、ルートからリーフまでのパスの長さが指定された値 k 未満であるようなパスのリーフノードをすべて削除する必要があります。次の例で具体的に確認してみましょう。

入力 −

K = 4

出力 −

解説

各パスは以下のとおりです。
1. A → B → C → E（長さ = 4）
2. A → B → C → F（長さ = 4）
3. A → B → D（長さ = 3）
4. A → G → H（長さ = 3）
5. A → B → I（長さ = 3）
ご覧のとおり、パス 3・4・5 の長さは 3 であり、これは与えられた k（= 4）より短いため、これらのパスのリーフノード（D、H、I）を削除します。
さらに、パス 4 と 5 では H と I を削除した結果、G 自身も新たなリーフノードとなり、その時点でのパスの長さは 2 になるため、今度はノード G を削除します。ここでプログラムは終了します。

この問題では、木を後順（ポストオーダー）走査で巡回し、パスの長さが k 未満であるリーフノードを再帰的に削除する関数を作成します。

解決のためのアプローチ

このアプローチでは、後順走査によって木を巡回しながら、パスの長さが k 未満となるリーフノードを再帰的に検出して削除し、この処理を続けていきます。

実装例

上記のアプローチを実装したC++コード

#include<bits/stdc++.h>
using namespace std;
struct Node{ // ノードの構造体
    char data;
    Node *left, *right;
};
Node *newNode(int data){ // 新しいノードの作成
    Node *node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
Node *trimmer(Node *root, int len, int k){
    if (!root) // root == NULL の場合はそのまま返す
        return NULL;
    root->left = trimmer(root->left, len + 1, k); // 左部分木を走査
    root->right = trimmer(root->right, len + 1, k); // 右部分木を走査
    if (!root->left && !root->right && len < k){
        delete root;
        return NULL;
    }
    return root;
}
Node *trim(Node *root, int k){
    return trimmer(root, 1, k);
}
void printInorder(Node *root){
    if (root){
        printInorder(root->left);
        cout << root->data << " ";
        printInorder(root->right);
    }
}
int main(){
    int k = 4;
    Node *root = newNode('A');
    root->left = newNode('B');
    root->right = newNode('G');
    root->left->left = newNode('C');
    root->left->right = newNode('D');
    root->left->left->left = newNode('E');
    root->left->left->right = newNode('F');
    root->right->left = newNode('H');
    root->right->right = newNode('I');
    printInorder(root);
    cout << "\n";
    root = trim(root, k);
    printInorder(root);
    return 0;
}

出力

E C F B D A H G I
E C F B A

コードの解説

このコードでは、再帰関数を用いて木を巡回し、左部分木と右部分木の状態を常に追跡しています。リーフノードに到達した時点で、そこまでのパスの長さをチェックし、長さが k 未満であればそのノードを削除して NULL を返します。条件を満たさない場合は、そのまま処理を続行します。

まとめ

本記事では、再帰を活用して「長さが K 未満のルートからリーフへのパス上のノードを削除する」という問題を解きました。この問題に対するC++プログラム、再帰的な考え方、そして完全な解法の流れについても学びました。同じロジックは、C、Java、Python などの他の言語でも同様に実装できます。本チュートリアルが皆さんの学習のお役に立てば幸いです。