★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公眾號：山青詠芝（shanqingyongzhi）
?博客園地址：山青詠芝（https://www.cnblogs.com/strengthen/）
?GitHub地址：https://github.com/strengthen/LeetCode
?原文地址：https://www.cnblogs.com/strengthen/p/10201562.html?
?如果鏈接不是山青詠芝的博客園地址，則可能是爬取作者的文章。
?原文已修改更新！強烈建議點擊原文地址閱讀！支持作者！支持原創(chuàng)！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Given a binary tree, we install cameras on the nodes of the tree.?

Each camera at?a node can monitor?its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: [0,0,null,0,0] Output: 1 Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: [0,0,null,0,null,0,null,null,0] Output: 2 Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

The number of nodes in the given tree will be in the range?[1, 1000].

Every?node has value 0.

---

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

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

計算監(jiān)控樹的所有節(jié)點所需的最小攝像頭數(shù)量。

?

示例 1：

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

示例 2：

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

提示：

給定樹的節(jié)點數(shù)的范圍是?[1, 1000]。

每個節(jié)點的值都是 0。

---

?52ms

1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public var val: Int 5 * public var left: TreeNode? 6 * public var right: TreeNode? 7 * public init(_ val: Int) { 8 * self.val = val 9 * self.left = nil 10 * self.right = nil 11 * } 12 * } 13 */ 14 class Solution { 15 func minCameraCover(_ root: TreeNode?) -> Int { 16 var ans:[Int] = mh(root) 17 return min(ans[1], ans[2]) 18 } 19 20 func mh(_ ro:TreeNode?)-> [Int] 21 { 22 if ro == nil 23 { 24 var ans:[Int] = [Int](repeating:0,count:3) 25 ans[1] = 1000000 26 return ans 27 } 28 var l:[Int] = mh(ro!.left) 29 var r:[Int] = mh(ro!.right) 30 var ans:[Int] = [Int](repeating:0,count:3) 31 ans[0] = l[2] + r[2]; 32 ans[1] = 1000000; 33 ans[2] = 1000000; 34 for i in 0..<3 35 { 36 for j in 0..<3 37 { 38 ans[1] = min(ans[1], l[i]+r[j]+1) 39 } 40 if i==0 {continue} 41 ans[2] = min(ans[2], l[1]+r[i]) 42 ans[2] = min(ans[2], l[i]+r[1]) 43 } 44 return ans 45 } 46 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/strengthen/p/10201562.html

總結(jié)

以上是生活随笔為你收集整理的[Swift]LeetCode968.监控二叉树 | Binary Tree Cameras的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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