C++의 이진 트리 카메라

<시간/>

이진 트리가 있다고 가정합니다. 트리의 노드에 카메라를 배치합니다. 이제 노드의 각 카메라는 상위, 자체 및 하위를 모니터링할 수 있습니다. 트리의 모든 노드를 모니터링하는 데 필요한 최소 카메라 수를 찾아야 합니다.

따라서 입력이 다음과 같으면 -

C++의 이진 트리 카메라

하나의 카메라만 모든 것을 추적하기에 충분하기 때문에 출력은 1이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

Covered라고 하는 TreeNode 유형의 집합 하나를 정의합니다(트리 노드에는 왼쪽, 오른쪽 및 데이터 필드가 있음).
solve() 함수를 정의하면 노드, 부모,
가 사용됩니다.
노드가 null이면 -
- 반환
해결(노드 왼쪽, 노드)
해결(노드 오른쪽, 노드)
(부모가 NULL과 같고 (노드, 노드 왼쪽, 노드 오른쪽) 아무 것도 덮이지 않으면 -
- (1만큼 증가)
- 덮힌 부분에 노드 삽입
- 덮힌 부분에 노드의 왼쪽 삽입
- 덮힌 부분에 노드 오른쪽 삽입
- 적용 대상에 부모 삽입
기본 방법에서 다음을 수행합니다.
답변 :=0
덮힌 부분에 NULL 삽입
해결(루트, NULL)
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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]