968.监控二叉树
给定一个二叉树,我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
贪心思路:
从下往上看,局部最优:让叶子节点的父节点安摄像头,所用摄像头最少
整体最优:全部摄像头数量所用最少
确定遍历顺序
可以使用后序遍历也就是左右中的顺序,这样就可以在回溯的过程中从下到上进行推导了
// 后序遍历,从下往上传递状态
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 = 0
function 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
};