虚拟机中做网站,网站系统目前运行稳定,汕头市城市建设总公司网站,torrent种子搜索引擎968.监控二叉树
力扣题目链接(opens new window)
给定一个二叉树#xff0c;我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。 贪心思路#xff1a;
从下往上看#xff0c;局部最…968.监控二叉树
力扣题目链接(opens new window)
给定一个二叉树我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。 贪心思路
从下往上看局部最优让叶子节点的父节点安摄像头所用摄像头最少 整体最优全部摄像头数量所用最少 确定遍历顺序
可以使用后序遍历也就是左右中的顺序这样就可以在回溯的过程中从下到上进行推导了 // 后序遍历从下往上传递状态let left dfs(n.left) // 获取传上来的状态let right dfs(n.right)
用三个数字来表示每个节点的状态
0该节点无覆盖1本节点有摄像头2本节点有覆盖 情况1左右节点都有覆盖 —— 本节点无覆盖
if(left 2 right 2){return 0}
情况2左右节点至少有一个无覆盖的情况 —— 本节点有摄像头
if(left 0 || right 0){res return 1}
情况3左右节点至少有一个有摄像头 —— 本节点有覆盖
if(left 1 || right 1){return 2}
特殊情况 最后遍历到根节点如果是无覆盖则根节点需要转换为有摄像头
if(dfs(root) 0){ // 处理最后的根节点res } 完整JS代码
var minCameraCover function(root) {let res 0function dfs(n){if(n null){return 2}// 后序遍历从下往上传递状态let left dfs(n.left) // 获取传上来的状态let right dfs(n.right)if(left 2 right 2){return 0}if(left 0 || right 0){res return 1}if(left 1 || right 1){return 2}return -1}if(dfs(root) 0){ // 处理最后的根节点res }return res
};
