題目描述
給定一個(gè)二叉樹，我們?cè)跇涞墓?jié)點(diǎn)上安裝攝像頭。
節(jié)點(diǎn)上的每個(gè)攝影頭都可以監(jiān)視其父對(duì)象抖誉、自身及其直接子對(duì)象。
計(jì)算監(jiān)控樹的所有節(jié)點(diǎn)所需的最小攝像頭數(shù)量衰倦。
解題思路
本題的思路是遞歸+貪心袒炉。對(duì)于樹中的每個(gè)節(jié)點(diǎn)，要判斷其是否放置攝像頭樊零，可以先看它左右孩子的狀態(tài)我磁。
-
節(jié)點(diǎn)的狀態(tài)：
a. 沒有被監(jiān)測(cè)到
b. 被檢測(cè)到但是沒有放置攝像頭
c. 放置了攝像頭
我們采用貪心的思想，對(duì)于每個(gè)節(jié)點(diǎn)能不放攝像頭就不放攝像頭驻襟。而從左右孩子的狀態(tài)夺艰，我們可以判斷該節(jié)點(diǎn)是否放攝像頭：
- 左右孩子有沒被監(jiān)測(cè)到，則沒辦法沉衣，只能在該節(jié)點(diǎn)放置攝像頭郁副。
- 左右孩子都被檢監(jiān)測(cè)了，但是都沒有放置攝像頭豌习，則在該節(jié)點(diǎn)可以不放置攝像頭存谎，等著被其父節(jié)點(diǎn)監(jiān)測(cè)。
- 左右孩子中至少有一個(gè)放置了攝像頭肥隆，那么該節(jié)點(diǎn)一定被監(jiān)測(cè)到了既荚，不用放置攝像頭。
而如果一個(gè)節(jié)點(diǎn)是空節(jié)點(diǎn)栋艳，那么它應(yīng)該被判斷成狀態(tài)b恰聘。因?yàn)槠涓腹?jié)點(diǎn)沒有必要為了監(jiān)測(cè)空節(jié)點(diǎn)而放置攝像頭，而如果空節(jié)點(diǎn)的狀態(tài)為a的話吸占，根據(jù)上述規(guī)則就必須在其父節(jié)點(diǎn)放置攝像頭了晴叨。
如此，對(duì)于一顆樹旬昭，只需對(duì)其后序遍歷篙螟，然后遞歸地判斷每顆節(jié)點(diǎn)是否應(yīng)該放置攝像頭，然后再返回其狀態(tài)问拘，就可以啦~
代碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int sum;
// 0: 無覆蓋
// 1: 有覆蓋
// 2: 有攝像頭
int dfs(TreeNode* root){
if (root == NULL)
return 1;
int left_top = dfs(root->left);
int right_top = dfs(root->right);
if (left_top == 0 || right_top == 0){
sum++;
return 2;
}
if (left_top == 2 || right_top == 2){
return 1;
}
return 0;
}
int minCameraCover(TreeNode* root) {
sum = 0;
int top = dfs(root);
if (top == 0)
sum++;
return sum;
}
};
