C++で二分木をカメラで監視する：必要な最小カメラ台数を求めるアルゴリズム

問題概要

二分木が与えられ、木のノードにカメラを設置することを考えます。あるノードに置かれたカメラは、その親ノード・自分自身・子ノードの3つを監視することができます。このとき、木のすべてのノードを監視するために必要となるカメラの最小台数を求めるのが本問題の目的です。

例えば、入力が下図のような木だった場合を考えてみましょう。

この場合の出力は 1 になります。わずか1台のカメラで、すべてのノードを監視できるからです。

解法のアプローチ

この問題は、葉に近いノードから順に判断していく貪欲法（グリーディー法）と再帰を組み合わせることで、効率的に解くことができます。基本的な考え方は「子孫側でカバーできるなら親にカメラを置かない」というものです。

手順

• TreeNode 型（左・右の子ポインタと値を持つ）の要素を格納する集合 covered を定義します。これは「すでに監視済みのノード」を管理するためのものです。
• 関数 solve(node, parent) を定義します。
• node が NULL の場合は何もせずに return します。
• solve(ノードの左の子, ノード)、solve(ノードの右の子, ノード) を再帰的に呼び出し、まず葉側を処理します。
• その後、次の条件のいずれかに該当する場合にカメラを設置します。
  • 親が NULL（＝現在のノードがルート）であり、node 自身が未カバーである
  • 左の子または右の子のいずれかが未カバーである
• カメラを設置する際は、ans を1増やした上で、node 自身・左の子・右の子・親をすべて covered に追加します。

メイン処理の流れ

• ans を 0 で初期化します。
• covered に NULL を挿入しておきます（NULL は常にカバー済みとして扱うことで、境界条件を簡潔にします）。
• solve(root, NULL) を呼び出します。
• 最後に ans を返します。

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;
    }
};
class Solution {
    public:
    set<TreeNode*> covered;
    int ans;
    int minCameraCover(TreeNode* root){
        covered.clear();
        ans = 0;
        covered.insert(NULL);
        solve(root, NULL);
        return ans;
    }
    void solve(TreeNode* node, TreeNode* parent){
        if (!node)
        return;
        solve(node->left, node);
        solve(node->right, node);
        if ((parent == NULL && covered.find(node) == covered.end())
        || covered.find(node->left) == covered.end()
        || covered.find(node->right) == covered.end()) {
            ans++;
            covered.insert(node);
            covered.insert(node->left);
            covered.insert(node->right);
            covered.insert(parent);
        }
    }
};
main(){
    Solution ob;
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(1);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(1);
    cout << (ob.minCameraCover(root));
}

入力

[1,1,NULL,1,1]

出力

1

計算量について

この解法では、木の各ノードを一度だけ訪問するため、時間計算量は O(n)（n はノード数）、空間計算量も covered 集合の管理分を含めて O(n) となります。後行順（ボトムアップ）で処理することで、カメラの設置判断を各ノードで1回だけ行える点が、このアルゴリズムのポイントです。