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
};