文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個(gè)二叉樹，我們?cè)跇涞墓?jié)點(diǎn)上安裝攝像頭。

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

計(jì)算監(jiān)控樹的所有節(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è)攝像頭來監(jiān)視樹的所有節(jié)點(diǎn)。 上圖顯示了攝像頭放置的有效位置之一。提示： 給定樹的節(jié)點(diǎn)數(shù)的范圍是 [1, 1000]。 每個(gè)節(jié)點(diǎn)的值都是 0。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binary-tree-cameras
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 節(jié)點(diǎn)只有3種狀態(tài)
• 1 表示被監(jiān)控，但是實(shí)際沒有camera
• 2 表示被監(jiān)控，有camera
• 0 表示需要被監(jiān)控
• 左右節(jié)點(diǎn)共計(jì)9種情況，分類討論

class Solution {int mins = 0; public:int minCameraCover(TreeNode* root) {if(!root) return 0;int l = dfs(root);if(l == 0)mins++;return mins;}int dfs(TreeNode* root){ // 1表示被監(jiān)控，但是實(shí)際沒有camera// 2表示被監(jiān)控，有camera// 0 表示需要被監(jiān)控if(!root)return 1;//沒有節(jié)點(diǎn)了相當(dāng)于監(jiān)控了int l = dfs(root->left);int r = dfs(root->right);if(l==0 || r==0)//5種情況{mins++;//左右子節(jié)點(diǎn)有任意一個(gè)需要被監(jiān)控return 2;//節(jié)點(diǎn)安裝攝像頭}else if(l==1 && r==1)//1種情況，左右子節(jié)點(diǎn)都被監(jiān)控了return 0;//本節(jié)點(diǎn)無須安裝，但是需要被監(jiān)控else//12，21，22{ // 左右子節(jié)點(diǎn)有任一為2（攝像頭）return 1;//節(jié)點(diǎn)處于被監(jiān)控狀態(tài)}} };

24 ms 20.6 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 968. 监控二叉树（DFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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