###### tags: `LeetCode` `Recursion` `Tree` `DFS` `Hard`
# LeetCode #968 [Binary Tree Cameras](https://leetcode.com/problems/binary-tree-cameras/)
### (Hard)

給定一個二元樹，我們在樹的節點上安裝相機。

節點上的每個相機都可以監視其父對象、自身及其直接子對象。

計算監控樹的所有節點所需的最小相機數量。

---
若子節點與父節點中需要選一個節點放置相機, 那父節點永遠是更好的選擇(因為還可以同時監控到祖父節點)

這題中有三個角色:
0:代表節點是葉節點
1:代表為父節點, 左右子節點中至少有一個的值為0, 在節點值為1的節點上要放相機
2:空節點或是其子節點的值為1, 此時不用放相機

處理完根結點的左右子樹後, 判斷根結點的值(DFS函式還沒有處理), 若root的值為0(左右子節點的值為2或0), 此時root節點也需要再放一個相機。

這種需要掌控整個結構情況才能做出判斷的題型, 使用DFS最為恰當, 因為相較於從頭開始考慮, 先處理最底層的節點再往上層走不會遇到需要修改之前的判斷的情況。

---

class Solution {
public:
    // 0:leaf 1:parent with camera 2:parent and its child is camera or null node
    int ans=0;
    int minCameraCover(TreeNode* root) {
        return (dfs(root)==0?1:0)+ans;
    }
    int dfs(TreeNode* node){
        if(!node)return 2;
        int left=dfs(node->left);
        int right=dfs(node->right);
        if(left==0||right==0){
            ans++;
            return 1;
        }
        return left==1||right==1?2:0;
    }
};