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

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

計算監控樹的所有節點所需的最小攝像頭數量。

?

示例 1：

輸入：[0,0,null,0,0] 輸出：1 解釋：如圖所示，一臺攝像頭足以監控所有節點。

示例 2：

輸入：[0,0,null,0,null,0,null,null,0] 輸出：2 解釋：需要至少兩個攝像頭來監視樹的所有節點。 上圖顯示了攝像頭放置的有效位置之一。

提示：

給定樹的節點數的范圍是?[1, 1000]。

每個節點的值都是 0。

遞歸

本題以二叉樹為背景，不難想到用遞歸的方式求解。本題的難度在于如何從左、右子樹的狀態，推導出父節點的狀態。

為了表述方便，我們約定：如果某棵樹的所有節點都被監控，則稱該樹被「覆蓋」。

假設當前節點為 $\text{root}$，其左右孩子為 $\text{left},\text{right}$。如果要覆蓋以 $\text{root}$ 為根的樹，有兩種情況：

• 若在 $\text{root}$ 處安放攝像頭，則孩子 $\text{left},\text{right}$ 一定也會被監控到。此時，只需要保證 $\text{left}$ 的兩棵子樹被覆蓋，同時保證 $\text{right}$ 的兩棵子樹也被覆蓋即可。
• 否則， 如果 $\text{root}$ 處不安放攝像頭，則除了覆蓋 $\text{root}$ 的兩棵子樹之外，孩子 $\text{left},\text{right}$ 之一必須要安裝攝像頭，從而保證 $\text{root}$ 會被監控到。

根據上面的討論，能夠分析出，對于每個節點 $\text{root}$ ，需要維護三種類型的狀態：

• 狀態 $a$：$\text{root}$ 必須放置攝像頭的情況下，覆蓋整棵樹需要的攝像頭數目。
• 狀態 $b$：覆蓋整棵樹需要的攝像頭數目，無論 $\text{root}$ 是否放置攝像頭。
• 狀態 $c$：覆蓋兩棵子樹需要的攝像頭數目，無論節點 $\text{root}$ 本身是否被監控到。

根據它們的定義，一定有 $a\ge b\ge c$。

對于節點 $\text{root}$ 而言，設其左右孩子 $\text{left},\text{right}$ 對應的狀態變量分別為 (la,lb,lc)(l_a,l_b,l_c)(la?,lb?,lc?) 以及 (ra,rb,rc)(r_a,r_b,r_c)(ra?,rb?,rc?)。根據一開始的討論，我們已經得到了求解 $a,b$ 的過程：

• a=lc+rc+1a = l_c + r_c + 1a=lc?+rc?+1
• b=min?(a,min?(la+rb,ra+lb))b = \min(a, \min(l_a + r_b, r_a + l_b))b=min(a,min(la?+rb?,ra?+lb?))

對于 $c$ 而言，要保證兩棵子樹被完全覆蓋，要么 $\text{root}$ 處放置一個攝像頭，需要的攝像頭數目為 $a$；要么 $\text{root}$ 處不放置攝像頭，此時兩棵子樹分別保證自己被覆蓋，需要的攝像頭數目為 lb+rbl_b + r_blb?+rb?。

需要額外注意的是，對于 $\text{root}$ 而言，如果其某個孩子為空，則不能通過在該孩子處放置攝像頭的方式，監控到當前節點。因此，該孩子對應的變量 $a$ 應當返回一個大整數，用于標識不可能的情形。

最終，根節點的狀態變量 $b$ 即為要求出的答案。

代碼

def minCameraCover(self, root: TreeNode) -> int:def dfs(root: TreeNode) -> List[int]:if not root:return [float('inf'), 0, 0]la, lb, lc = dfs(root.left)ra, rb, rc = dfs(root.right)a = lc + rc + 1b = min(a, la + rb, ra + lb)c = min(a, lb + rb)return [a, b, c]a, b, c = dfs(root)return b

總結

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

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