給定一個(gè)二叉樹(shù)，我們?cè)跇?shù)的節(jié)點(diǎn)上安裝攝像頭。
節(jié)點(diǎn)上的每個(gè)攝影頭都可以監(jiān)視其父對(duì)象、自身及其直接子對(duì)象。
計(jì)算監(jiān)控樹(shù)的所有節(jié)點(diǎn)所需的最小攝像頭數(shù)量。

示例 1：

輸入：[0,0,null,0,0]
輸出：1
解釋：如圖所示，一臺(tái)攝像頭足以監(jiān)控所有節(jié)點(diǎn)。
示例 2：

輸入：[0,0,null,0,null,0,null,null,0]
輸出：2
解釋：需要至少兩個(gè)攝像頭來(lái)監(jiān)視樹(shù)的所有節(jié)點(diǎn)。 上圖顯示了攝像頭放置的有效位置之一。

提示：

給定樹(shù)的節(jié)點(diǎn)數(shù)的范圍是 [1, 1000]。
每個(gè)節(jié)點(diǎn)的值都是 0。

————————————————————————————————————————————————————————
題目要求最小攝像頭數(shù)目，如果從頭節(jié)點(diǎn)開(kāi)始看，就只能省一個(gè)攝像頭，而如果從葉子節(jié)點(diǎn)開(kāi)始看，就可以省下指數(shù)級(jí)的攝像頭數(shù)目；
所以可以確定遍歷順序是從葉子節(jié)點(diǎn)開(kāi)始向上遍歷，讓葉子節(jié)點(diǎn)的父節(jié)點(diǎn)裝攝像頭即可；
很容易想到是后序遍歷，根據(jù)貪心思想有：
局部最優(yōu)：葉子節(jié)點(diǎn)的父節(jié)點(diǎn)安攝像頭，所用攝像頭最少；
全局最優(yōu)：整體二叉樹(shù)所用攝像頭最少；

然后該考慮裝攝像頭的情況了，這里需要考慮每個(gè)節(jié)點(diǎn)可能的狀態(tài)，有三種：
1，有攝像頭覆蓋
2，沒(méi)有攝像頭覆蓋
3，有攝像頭

注意：這里“沒(méi)有攝像頭”狀態(tài)就是1和2了；

所以可以用三個(gè)數(shù)字表示節(jié)點(diǎn)狀態(tài)：
0：該節(jié)點(diǎn)無(wú)覆蓋
1：該節(jié)點(diǎn)有攝像頭
2：該節(jié)點(diǎn)有覆蓋

這里還需要考慮一點(diǎn)：空節(jié)點(diǎn)怎么辦？（終止條件）
空節(jié)點(diǎn)如果是沒(méi)有覆蓋狀態(tài)，那么葉節(jié)點(diǎn)就得有攝像頭，所以我們需要將空節(jié)點(diǎn)賦為有覆蓋的狀態(tài)；

整個(gè)遞歸函數(shù)整體框架有了，接下來(lái)是每一層的邏輯情況，有四種：
1，左孩子和右孩子都有覆蓋（2），那么父節(jié)點(diǎn)就需要是無(wú)覆蓋狀態(tài)（0）
2，左孩子和右孩子至少有一個(gè)沒(méi)有覆蓋，那么父節(jié)點(diǎn)就需要是有攝像頭狀態(tài)（1）
3，左孩子和右孩子至少有一個(gè)有攝像頭，那么父節(jié)點(diǎn)就需要是有覆蓋的狀態(tài)（2）
4，頭節(jié)點(diǎn)沒(méi)有覆蓋，那么需要單獨(dú)給它加一個(gè)攝像頭；

分析完了，代碼如下：

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution { public:int ans = 0;//0：無(wú)覆蓋 1：有攝像頭 2：有覆蓋int traverse(TreeNode* root) {if (!root) return 2;int left = traverse(root -> left);int right = traverse(root -> right);//情況二if (!left || !right) {ans++;return 1;}//情況三if (left == 1 || right == 1) {return 2;}//情況一if (left == 2 && right == 2) {return 0;}return -1;}int minCameraCover(TreeNode* root) {//情況四if (!traverse(root)) {ans++;}return ans;} };

總結(jié)

以上是生活随笔為你收集整理的968. 监控二叉树（递归+贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。