給定一個二叉樹，我們在樹的節(jié)點上安裝攝像頭。

創(chuàng)新互聯(lián)建站堅持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站制作、網(wǎng)站設(shè)計、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的欽州網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

節(jié)點上的每個攝影頭都可以監(jiān)視其父對象、自身及其直接子對象。

計算監(jiān)控樹的所有節(jié)點所需的最小攝像頭數(shù)量。

---

思路：

? 1、要盡可能的少安裝攝像頭，那么攝像頭不可能安裝在葉子節(jié)點上，從葉子節(jié)點開始從下往上遍歷，用左右中的后序遍歷方式；

? 2、每個節(jié)點有3種狀態(tài)，無覆蓋、有攝像頭、有覆蓋，分別設(shè)為0、1、2；

? 3、確定好遍歷順序后，終止條件，如果遇到空節(jié)點，則默認為有覆蓋；

? 4、單層邏輯：對左右孩子的狀態(tài)進行判斷，來確定父節(jié)點的狀態(tài)

? 主要分成了4種情況：(1)左右孩子均為有覆蓋，父節(jié)點為無覆蓋情況；

(2)左右孩子只要有一個無覆蓋，則需要在父節(jié)點加一個攝像頭；

(3)左右孩子只有有一個攝像頭，則父節(jié)點就為有覆蓋情況；

(4)最后需要對根結(jié)點進行判斷，如果無覆蓋，則需要再加一個攝像頭。

class Solution {
private:
    int result;
public:
    int traversal(TreeNode* root){
        //終止條件
        if(root==NULL)  return 2;
        //遍歷順序：左右中 后序遍歷
        int left=traversal(root->left);
        int right=traversal(root->right);
        //中
        if(left==2&&right==2)   return 0;//左右孩子均為有覆蓋，父節(jié)點為無覆蓋情況
        if(left==0||right==0)
        {
            result++;
            return 1;//左右孩子只要有一個無覆蓋，則需要在父節(jié)點加一個攝像頭
        }   
        if(left==1||right==1)   return 2;//左右孩子只有有一個攝像頭，則父節(jié)點就為有覆蓋情況
        return -1;//不會走到這一步
    }
    int minCameraCover(TreeNode* root) {
        result=0;
        //對根結(jié)點進行判斷，如果無覆蓋，則需要再加一個攝像頭
        if(traversal(root)==0)  result++;
        return result;
    }
};

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

文章標題：【20221204】【每日一題】監(jiān)控二叉樹-創(chuàng)新互聯(lián)
文章出自：http://weahome.cn/article/cshihi.html