LeetCode 968.监控二叉树 (hard)
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
};