leetcode.968 监控二叉树

给定一个二叉树,我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1:
输入:[0,0,null,0,0]
输出:1
解释:如图所示,一台摄像头足以监控所有节点。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-cameras

  • 如果是空节点返回1
  • 叶子节点返回0
  • 子节点中有叶子节点res++,返回2
  • 子节点中没有叶子节点并且有监控节点返回1
class Solution {
    public int minCameraCover(TreeNode root) {
       if(helper(root) == 0){
           res ++;
       }
       return res;
    }
    int res = 0;
       int helper(TreeNode root){
        if(root == null){
            return 1;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        if(left == 0 || right == 0){
            res++;
            return 2;
        }
        if(left == 1 && right ==1){
            return 0;
        }
        if(left + right >= 3){
            return 1;
        }
        return -100;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。