C++のバイナリツリーカメラ

二分木があるとしましょう。ツリーのノードにカメラを配置します。これで、ノードの各カメラは、その親、それ自体、およびその子を監視できます。ツリーのすべてのノードを監視するために必要なカメラの最小数を見つける必要があります。

したがって、入力が-

すべてを追跡するには1台のカメラで十分なので、出力は1になります。

これを解決するには、次の手順に従います-

• タイプTreeNodeのcoveredと呼ばれる1つのセットを定義します（ツリーノードには左、右、およびデータフィールドがあります）

• 関数solve（）を定義します。これはノード、親、

  を取ります

• ノードがnullの場合、-

  • 戻る

• 解決（ノードの左側、ノード）

• 解決（ノードの右側、ノード）

• （親がNULLと同じで、（ノード、ノードの左側、ノードの右側）何もカバーされていない場合、-

  • （ansを1増やします）

  • カバーされたノードにノードを挿入します

  • ノードの左側をカバーに挿入します

  • ノードの右側をカバーに挿入します

  • 親をカバーに挿入

• メインの方法から、次のようにします。

• ans：=0

• カバーにNULLを挿入

• 解決（ルート、NULL）

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

#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