解題思路: 由于葉子節點一定不要安裝監視器,這樣才能使總監視器數量比較少,因此需要從下往上進行判斷當前節點的狀態(共:3種狀態):

• 0: 當前節點安裝了監視器
• 1: 當前節點可觀,但沒有安裝監視器
• 2: 當前節點不可觀

對于空節點,我們認為是可觀,但沒有安裝監視器,因此,葉子節點就為不可觀的了,設想一個節點的左右孩子(為空)都可觀且沒有安裝監視器,那該節點必然是不可觀即2

有了以上對空節點和葉子節點的處理,我們再來正式分析非終端節點:

• 若一個節點的左孩子或右孩子不可觀,那么該節點必然不可觀,需要安裝監視器,因此返回0狀態
• 若一個節點的左孩子或右孩子都可觀且至少有一個安裝了監視器,那么該節點必然是可觀的,返回1狀態
• 若一個節點的左右孩子都可觀且沒安裝監視器,那么該節點必然是不可觀的,返回2狀態

記住,我們以上的分析都是基于從整個二叉樹的葉子節點往根部,即從下往上進行,而且要做的就是將不可觀的節點變得可觀才行(因此要根據左右孩子的節點的狀態來判斷當前節點狀態并做出調整)

這里可能會有疑惑,以上的第一條得出當前節點不可觀,然后安裝了監視器,而第三條也得出當前節點不可觀,但卻沒有安裝監視器,而是直接返回的2狀態(當前節點不可觀).這是為什么?

因為,對于第一條,因為左右孩子都不可觀,為了讓左右孩子都可觀,則必須給當前節點安裝監視器才行,而第三條中,左右孩子都是可觀的(沒有安裝監視器),當前節點的可以直接返回不可觀狀態,因為后面可以由他的父節點進行攝像頭安裝,使其變得可觀.

方法一:遞歸

// 0：該節點安裝了監視器 1：該節點可觀，但沒有安裝監視器 2：該節點不可觀int monitor = 0;int state(TreeNode* node){if (node == nullptr) return 1;int left = state(node->left);int right = state(node->right);// 該節點為0的情況if (left == 2 || right == 2){monitor++; // 由于左或右節點不可觀,則需要給當前節點安裝監視器,為0狀態return 0;} // 為1的情況else if (left == 0 || right == 0)return 1; // 當(left!=2&&right!=2)時,才會進行該判斷,也就是左右節點一定是可觀的,再判斷是否有一個安裝了監視器,如有安裝,則當前節點就不需要安裝監視器也可觀了,為1狀態// 為2的情況else // 其他:黨(left!=2&&right!=2)&&(left!=0&&right!=0),即left==1&&right==1時,左右節點都可觀,但沒有監視器,當前節點不可觀,為2狀態return 2;}int minCameraCover(TreeNode *root){if (root == nullptr) return 0;if (state(root) == 2) monitor++; // 如果根節點為2的狀態,需要加一個監視器return monitor;}

?注意:這里的if,else if,else的順序是不能變的,先判斷左右都是不可觀的,再就是都可觀,左或右至少有一個為監視器,最后才是都可觀都無監視器.

轉載于:https://www.cnblogs.com/brianyi/p/10801186.html

總結

以上是生活随笔為你收集整理的【leetcode 968. 监控二叉树】解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。