网络异常，图片无法展示
|
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：
网络异常，图片无法展示
|
输入： [0,0,null,0,0] 输出： 1 解释： 如图所示，一台摄像头足以监控所有节点。 复制代码
示例 2：
网络异常，图片无法展示
|
输入： [0,0,null,0,null,0,null,null,0] 输出： 2 解释： 需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。 复制代码
提示：
- 给定树的节点数的范围是
[1, 1000]。 - 每个节点的值都是 0。
推导求解
要想安装的摄像头数量最小，则应该尽可能的在父节点安装摄像头
这样就可以让两个子树共用父节点的摄像头
所以可以从叶子节点向上反推需要摄像头的最小数量
推导摄像头数量的规则如下：
如果当前为叶子节点，为了最大程度利用摄像头的覆盖性
此时应该在其父节点放置摄像头
利用父节点的摄像头覆盖当前叶子节点
因为在二叉树中，每个节点的值都是 0，通过标记节点值 val = 2 标识当前节点已安装摄像头
val = 1 标识当前节点通过其父节点或者子节点摄像头被覆盖监视
最后，所有节点值 val = 2 的节点就是需要安装摄像头的节点，它们的数量就是监控二叉树需要的最小摄像头数量。
动画演示如下：
网络异常，图片无法展示
|
代码如下：
// 递归记录父节点，回溯推导摄像头数量 var minCameraCover = function(root) { let res = 0; function preorder(node){ // 如果有左子树 if(node.left){ // 定义parent属性指向当前节点 node.left.parent = node; // 递归处理左子树 preorder(node.left); } // 如果有右子树 if(node.right){ // 定义parent属性指向当前节点 node.right.parent = node; // 递归处理右子树 preorder(node.right); } // 如果当前节点放置摄像头 if(node.val === 2){ // 数量加1 res++; // 如果有父节点且父节点值为0,将父节点值 val = 1,标识父节点可以被监视到 // 如果父节点已经放置了摄像头，不能修改父节点val if(node.parent&&node.parent.val===0) node.parent.val = 1; }else if(node.val === 0){ // 如果当前节点没有被监视到 // 如果有父节点，优先让父节点放置摄像头，覆盖当前节点 if(node.parent) node.parent.val = 2,node.val = 1; // 否则只能自己放置摄像头 else node.val = 2,res++; } } // 递归处理二叉树 preorder(root); // 返回结果值 return res; }; 复制代码
动态规划求解
涉及到求最优解的题，都可以用动态规划解题
有了题解1的基础，这里我们可以推导出状态定义如下：
dp[i][j] 表示监控以 j 为根节点的子树所需要的摄像头数量 i 表示 j 的父节点，0 表示当前节点不放置摄像头，1 表示当前节点放置摄像头 每个节点有如下四种状态： dp[0][0] 覆盖当前子树父节点不放置摄像头，根节点不放置摄像头的摄像头数量 dp[0][1] 覆盖当前子树父节点不放置摄像头，根节点放置摄像头的摄像头数量 dp[1][0] 覆盖当前子树父节点放置摄像头，根节点不放置摄像头的摄像头数量 dp[1][1] 覆盖当前子树父节点放置摄像头，根节点放置摄像头的摄像头数量 复制代码
状态转移方程如下：
l 为左子树 dp,r 为右子树 dp dp[0][0] = Math.min(l[0][0]+r[0][1],l[0][1]+r[0][0],l[0][1]+r[0][1]); dp[1][0] = Math.min(dp[0][0],l[0][0]+r[0][0]); dp[0][1] = Math.min(l[1][0]+r[1][0],l[1][1]+r[1][0],l[1][0]+r[1][1],l[1][1]+r[1][1])+1; dp[1][1] = dp[0][1]; 复制代码
代码如下：
var minCameraCover = function(root) { function getDp(root){ const dp = [[],[]]; if(root === null){ dp[0][0] = 0; dp[0][1] = 10000; dp[1][0] = 0; dp[1][1] = 10000; return dp; } if(root.left===null&&root.right===null){ dp[0][0] = 10000; dp[0][1] = 1; dp[1][0] = 0; dp[1][1] = 1; return dp; } const l = getDp(root.left), r = getDp(root.right); dp[0][0] = Math.min(l[0][0]+r[0][1],l[0][1]+r[0][0],l[0][1]+r[0][1]); dp[1][0] = Math.min(dp[0][0],l[0][0]+r[0][0]); dp[0][1] = Math.min(l[1][0]+r[1][0],l[1][1]+r[1][0],l[1][0]+r[1][1],l[1][1]+r[1][1])+1; dp[1][1] = dp[0][1]; return dp; } const dp = getDp(root); return Math.min(dp[0][1],dp[0][0]); } 复制代码
以上代码中利用了一个技巧：
当某种情况不合法时（例如：在空节点放置摄像头），返回一个极大值，标识当前状态不合理（因为给定数的节点范围是1~1000，所以这里返回10000标识该操作不合法）。
至此我们就完成了 leetcode-968-监控二叉树
如有任何问题或建议，欢迎留言讨论！
