C++で二分木を剪定するプログラム：1を含まない部分木の削除方法

問題の概要

ここでは、各ノードの値が「0」または「1」のいずれかである二分木を扱います。求めるのは、値「1」を一切含まないすべての部分木を削除した後の木です。たとえば、次のような木が与えられた場合を考えてみましょう。

剪定後の木では、子孫のどこにも「1」を持たない部分木が丸ごと取り除かれます。重要なのは、葉ノードだけでなく、内部ノードであっても、その下の部分木全体に1が存在しなければ削除対象になるという点です。

解決のためのアプローチ

この問題は、再帰を用いることで簡潔に解けます。ノードを受け取る再帰メソッド solve()（実装例では pruneTree()）を定義し、以下の手順で処理を進めます。

• ノードがNULLであれば、そのままNULLを返します。
• ノードの左の子に対して再帰的に solve() を呼び出し、その戻り値を新しい左の子として設定します。
• 右の子についても同様に再帰呼び出しを行い、結果を右の子として設定します。
• 処理後に左の子・右の子がともにNULLであり、かつノードの値が0である場合は、その部分木に1が存在しないためNULLを返して削除します。
• 上記に該当しない場合は、現在のノードをそのまま返します。

この処理は木の末端（葉）から根に向かってボトムアップに進むため、各ノードを1回だけ訪問すれば済みます。ノード数をnとすると、時間計算量はO(n)、空間計算量は再帰の深さ分となり、最悪ケースでO(n)です。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = NULL;
        right = NULL;
    }
};
void inorder(TreeNode *root){
    if(root){
        inorder(root->left);
        cout << root->val << ", ";
        inorder(root->right);
    }
}
class Solution {
    public:
    TreeNode* pruneTree(TreeNode* node) {
        if(!node)return NULL;
        node->left = pruneTree(node->left);
        node->right = pruneTree(node->right);
        if(!node->left && !node->right && !node->val){
            return NULL;
        }
        return node;
    }
};
main(){
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(1);
    root->right = new TreeNode(0);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(1);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(1);
    root->left->left->left = new TreeNode(0);
    Solution ob;
    inorder(ob.pruneTree(root));
}

コードのポイント

• TreeNodeクラス：ノードの値 val と、左右の子へのポインタ left / right を持ちます。
• inorder関数：中間順巡回（左→根→右）でノードの値を出力し、剪定結果を確認するために使用します。
• pruneTreeメソッド：剪定処理の本体です。まず子ノードを処理してから自分自身の必要性を判定するという、後順（ポストオーダー）の考え方に基づいています。

入力

TreeNode *root = new TreeNode(1);
root->left = new TreeNode(1);
root->right = new TreeNode(0);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(1);
root->right->left = new TreeNode(0);
root->right->right = new TreeNode(1);
root->left->left->left = new TreeNode(0);

出力

1, 1, 1, 1, 0, 1,

出力結果から、左端の孤立した「0」の葉ノードや、右部分木内にある「0」のみの葉ノードが正しく削除され、1を含む部分木だけが残っていることが確認できます。これにより、要求どおりの剪定が実現できています。