fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Node{
  6.     int val;
  7.     Node *left;
  8.     Node *right;
  9.     Node(int x)
  10.     {
  11.         val = x;
  12.         left = nullptr;
  13.         right = nullptr;
  14.     }
  15. };
  16.  
  17. int minCameras(Node* root, int& cameras) 
  18. {
  19.     if (root == nullptr) {
  20.         return 1; 
  21.     }
  22.  
  23.     int left_state = minCameras(root->left, cameras);
  24.     int right_state = minCameras(root->right, cameras);
  25.  
  26.     // Trường hợp 1: Cả hai con đều đã được bao phủ
  27.     if (left_state == 1 && right_state == 1) {
  28.         return 0; // Node hiện tại chưa được bao phủ và không có camera
  29.     }
  30.  
  31.     // Trường hợp 2: Ít nhất một trong hai con chưa được bao phủ
  32.     if (left_state == 0 || right_state == 0) {
  33.         cameras++; // Đặt một camera tại node hiện tại để bao phủ nó và các con
  34.         return 2;
  35.     }
  36.  
  37.     // Trường hợp 3: Ít nhất một trong hai con có camera
  38.     if (left_state == 2 || right_state == 2) {
  39.         return 1; // Node hiện tại đã được bao phủ bởi camera của con
  40.     }
  41.  
  42.     // Trường hợp mặc định (không nên xảy ra nếu logic đúng)
  43.     return -1;
  44. }
  45.  
  46. int minCameraCover(Node* root) {
  47.     int cameras = 0;
  48.     if (minCameras(root, cameras) == 0) {
  49.         cameras++; 
  50.         // Nếu root chưa được bao phủ sau khi duyệt, cần đặt một camera tại root
  51.     }
  52.     return cameras;
  53. }
  54.  
  55. int main() {
  56.     // Xây dựng một cây nhị phân ví dụ
  57.     Node* root = new Node(0);
  58.     root->left = new Node(0);
  59.     root->left->left = new Node(0);
  60.     root->left->right = new Node(0);
  61.     root->right = new Node(0);
  62.     root->right->right = new Node(0);
  63.  
  64.     cout << "So camera toi thieu: " << minCameraCover(root) << endl; // Output: 2
  65.  
  66.     // Xây dựng một cây nhị phân ví dụ khác
  67.     Node* root2 = new Node(0);
  68.     root2->left = new Node(0);
  69.     root2->left->left = new Node(0);
  70.     root2->left->left->left = new Node(0);
  71.     root2->left->left->left->right = new Node(0);
  72.  
  73.     cout << "So camera toi thieu: " << minCameraCover(root2) << endl; // Output: 2
  74.  
  75.     return 0;
  76. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
So camera toi thieu: 2
So camera toi thieu: 2
https://ideone.com/cugbMJ
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!