968. 监控二叉树(leetcode)

LXL's Blog / 2024-08-31 / 原文

https://leetcode.cn/problems/binary-tree-cameras/description/

结合二叉树的贪心题,思路较难想出

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    int res=0;

    public int minCameraCover(TreeNode root) {
        // 贪心:思路是摄像头能够监控上下两个方向,如果摄像头在根节点则浪费了上方向的检测
        // 若在叶子节点则浪费了下反向的检测,因此只能放根节点的子节点或者叶子结点的父节点
        // 由于根节点的子节点只有两个,而叶子节点的父节点有多个,从贪心的角度来想
        // 从叶子节点的父节点向上,隔两个放一个摄像头,比在根节点的子节点上检测到的节点的多
        // 因此确定选择从下往上推,而上面不用管摄像头是放在根还是跟的子节点上
        if(dfs(root)==0)res++; // 若根节点没被覆盖,则需要额外处理
        return res;
    }

    // 后序遍历,返回值是当前节点的状态,0无覆盖,1摄像头,2有覆盖
    int dfs(TreeNode root)
    {
        if(root==null)return 2;// 空节点视为有覆盖才不会出bug
        int left=dfs(root.left);
        int right=dfs(root.right);
        if(left == 2 && right == 2)return 0; // 左右都被覆盖了,父节点就是0,因为要隔两个才放摄像头
        if(left == 0 || right == 0)
        {
            res++; // 左右至少有一个是无覆盖,则需要一个摄像头
            return 1; 
        }
        if(left == 1 || right == 1)return 2; // 左右至少有一个摄像头
        // 永远不会走到这里
        return -1;

    }
}