กล้องวงจรปิดในต้นไม้แบบทวิภาค (Binary Tree Cameras) ใน C++

คำอธิบายโจทย์

วางกล้องที่โหนดต้นไม้ กล้องแต่ละตัวตรวจสอบ: parent, ตัวเอง, children หาจำนวนกล้องน้อยที่สุดครอบคลุมทุกโหนด

ตัวอย่าง

Tree: [1,1,null,1,1] → Output: 1

กล้อง 1 ตัวที่รากครอบคลุมทั้งต้นไม้

วิธีแก้ปัญหา

Greedy DFS (Post-order):

• covered set: โหนดที่ถูกครอบคลุม (รวม NULL)
• DFS ลงลึกไปก่อน (post-order)
• ถ้า parent=NULL และโหนด/ลูกไม่ได้ครอบคลุม → วางกล้องที่โหนดนี้
• Mark โหนด, ลูก, parent ว่าครอบคลุมแล้ว

การทำงานของโค้ด

#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 = 0;
    
    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.count(node)) 
           || !covered.count(node->left) 
           || !covered.count(node->right)) {
            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;
}

อินพุต

[1,1,NULL,1,1]

เอาต์พุต

1