leetcode968. 监控二叉树

news/2024/9/28 19:21:56 标签: 数据结构, 算法, leetcode, javascript

给定一个二叉树,我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例 1:

输入:[0,0,null,0,0]
输出:1
解释:如图所示,一台摄像头足以监控所有节点。

示例 2:

输入:[0,0,null,0,null,0,null,null,0]
输出:2
解释:需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。


提示:

  1. 给定树的节点数的范围是 [1, 1000]
  2. 每个节点的值都是 0。
javascript">/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minCameraCover = function(root) {
    const dfs = (root) => {
        if (!root) {
            return [Math.floor(Number.MAX_SAFE_INTEGER / 2), 0, 0];
        }
        const [la, lb, lc] = dfs(root.left);
        const [ra, rb, rc] = dfs(root.right);
        const a = lc + rc + 1;
        const b = Math.min(a, Math.min(la + rb, ra + lb));
        const c = Math.min(a, lb + rb);
        return [a, b, c];
    }

    return dfs(root)[1];
};
 


http://www.niftyadmin.cn/n/5681703.html

相关文章

AI名词扫盲

本篇章主要介绍一些AI研究方向的名词以及解释,后续会持续补充,名词解释与时间顺序无关,欢迎各位大佬们在评论区查漏补缺。 目录 AI(Artificial Intelligence,人工智能)卷积神经网络(CNN&#xf…

全局中断总开关位与各个中断源对应的寄存器使能位开启顺序

在微控制器中,中断总开关通常用来全局性地控制中断的使能和关闭。对于各个中断的位使能,则是用来单独控制每个中断源的使能状态。配置它们的先后关系通常遵循以下步骤: 1.全局中断禁能:首先,需要禁止中断总开关&#x…

.NET MAUI(.NET Multi-platform App UI)下拉选框控件

MAUI下拉选框控件详解: 在开发跨平台应用程序时,下拉选框(ComboBox)是一个极为常见且实用的控件,它允许用户从一组预定义的选项中选择一个。在.NET MAUI(.NET Multi-platform App UI)框架中&am…

【Threejs进阶教程-着色器篇】8. Shadertoy如何使用到Threejs-基础版

【Threejs进阶教程-着色器篇】8. Shadertoy如何使用到Threejs - 基础版 前七篇地址,建议按顺序学习致谢带我入门的[X01动力装甲]大佬本文适用范围怎么样在Shadertoy中画出正圆形shadertoy中的坐标系比例转换理解Shadertoy的fragCoord理解Shadertoy中的iResolution 转移Shaderto…

《二十一天》热度狂飙幕后真相原著小说好看还是剧好看

勇于突破,敢于尝试新类型,12集灾难求生/悬疑刑侦网剧《二十一天》,自9月26日爱奇艺迷雾剧场开播以来热度持续攀升。灾难开局、人性探底、悬疑推理,地上地下双线交叉进行的剧情渐入佳境,但网络评论褒贬不一,…

oracle 如何判断当前时间在27号到当月月底

在Oracle中&#xff0c;您可以使用TRUNC和LAST_DAY函数来判断当前时间是否在27号到当月月底之间。以下是一个SQL示例&#xff1a; SELECT CASE WHEN TRUNC(SYSDATE) > TRUNC(SYSDATE, DD) 26 AND TRUNC(SYSDATE) < LAST_DAY(SYSDATE) THEN 当前时间在27号到当月月底之间…

图灵完备-成对的麻烦

steam上有一个叫图灵完备&#xff08;turing complete&#xff09;的游戏&#xff0c;其中一个关卡比较有意思&#xff0c;故此记录&#xff0c;也就是“成对的麻烦”。 题目大意是匹配袜子的问题&#xff0c;有4个输入&#xff0c;只要其中两个位true&#xff0c;最终结果就返…

【系统规划与管理师】【案例分析】【考点】【问题篇】第10章 团队建设与管理

//自己整理的&#xff0c;仅具参考价值&#xff0c;一起加油吧~相信自己 尽力而为 【答案篇】 【系统规划与管理师】【案例分析】【考点】【答案篇】第10章 团队建设与管理 【问题篇】 第10章 团队建设与管理 1、IT服务团队应具有哪些特征&#xff1f;2、该服务团队处在IT…