Camera cây nhị phân trong C++

Cho cây nhị phân, đặt camera tại các nút. Mỗi camera giám sát nút cha, chính nó và các nút con. Tìm số camera tối thiểu để giám sát tất cả nút.

Ví dụ: cây như hình → chỉ cần 1 camera.

Giải pháp

DFS hậu thứ tự (post-order) với tập covered:

• Tập covered lưu các nút đã được giám sát (khởi tạo với NULL)
• Hàm solve(node, parent):
  • Nếu node null: return
  • Đệ quy left, right
  • Nếu (parent==NULL và node chưa covered) HOẶC (con trái chưa covered) HOẶC (con phải chưa covered):
    • Tăng ans++
    • Thêm node, left, right, parent vào covered
• Gọi solve(root, NULL), trả về ans

Ý tưởng: đặt camera ở cha của các lá chưa được giám sát (greedy bottom-up).

Ví dụ mã 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); 
        } 
    } 
}; 

int 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)); 
    return 0; 
}

Đầu vào

[1,1,NULL,1,1]

Đầu ra

1