打家劫舍Ⅲ(LeetCode-337)

简介: 打家劫舍Ⅲ(LeetCode-337)

打家劫舍Ⅲ(LeetCode-337)


题目

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。


除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。


给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。


示例 1:


输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7


示例 2:


输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9


提示:


树的节点数在 [1, 104] 范围内

0 <= Node.val <= 104


思路

树形数组


确定递归函数参数与返回值


返回偷和不偷两种状态下获得的金钱。下标0表示不偷当前节点获得的最大金额,下标1表示偷当前节点获得的最大金额

确定终止条件


遇到空节点,肯定返回 { 0 , 0 } 确定遍历顺序


必须后序遍历,因为要通过递归函数返回值后考虑

确定单层逻辑


如果偷当前节点


左右孩子不能偷,即左右孩子各取下标0的值相加

v a l 1 = c u r . v a l + l e f t [ 0 ] + r i g h t [ 0 ]

如果不偷当前节点


左右孩子可以考虑偷,但到底偷不偷还是要判断

v a l 2 = m a x ( l e f t [ 0 ] , l e f t [ 1 ] ) + m a x ( r i g h t [ 0 ] , r i g h t [ 1 ] )


测试用例



代码展示

class Solution
{
public:
    int rob(TreeNode *root)
    {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    vector<int> robTree(TreeNode *cur)
    {
        if (!cur)
        {
            return {0, 0};
        }
        vector<int> curleft = robTree(cur->left);
        vector<int> curright = robTree(cur->right);
        int val1 = cur->val + curleft[0] + curright[0];
        int val2 = max(curleft[0], curleft[1]) + max(curright[0], curright[1]);
        return {val2, val1};
    }
};
目录
相关文章
|
云安全 安全 网络安全
网络安全 | 什么是云安全?
云安全是应对企业外部和内部威胁的关键,它集合了多种程序和技術,确保云服务(如IaaS、PaaS、SaaS)的安全运行。云计算让企业能灵活扩展,但也带来数据安全管理挑战,包括可见性不足、多租户风险、访问控制困难和合规性问题。配置错误也是主要威胁。应对策略包括身份和访问管理(IAM)、数据丢失预防(DLP)、信息安全和事件管理(SIEM)以及业务连续性和灾难恢复计划。企业需构建安全的云计算框架,遵循网络安全框架,并利用云安全态势管理(CSPM)来防止错误配置造成的风险。
359 0
|
编解码 算法 开发者
新手主播实战教程:YY开播工具+OBS美颜插件配置,零基础实现专业级直播画质
本文面向对直播画质有高要求的开发者与专业主播,详解如何通过YY开播工具的虚拟摄像头功能,将其美颜能力无缝集成至OBS推流软件,弥补OBS原生美颜功能的不足。内容涵盖软硬件准备、核心对接步骤及YY美颜参数调优技巧,帮助用户实现专业级直播视觉效果,同时提供常见问题解答,确保配置顺利。
新手主播实战教程:YY开播工具+OBS美颜插件配置,零基础实现专业级直播画质
|
2月前
|
JavaScript 前端开发 测试技术
Playwright自动化测试系列课(4) | 异步加载克星:自动等待 vs 智能等待策略深度解析​
本文深度解析Playwright自动化测试中的等待策略,对比自动等待(零配置防御机制)与智能等待(精准控制异步场景)的核心差异。通过实战案例讲解等待机制的选择标准、常见失效原因及调试技巧,帮助开发者有效解决页面异步加载问题,提升测试脚本的稳定性和执行效率。
|
Linux 网络安全
suse 12 升级 OpenSSH-7.2p2 到 OpenSSH-8.4p1
suse 12 升级 OpenSSH-7.2p2 到 OpenSSH-8.4p1
404 0
|
存储 运维 监控
研发视角:一个需求应该怎么拆解与实现?
本文介绍了在软件研发过程中,开发人员接到需求后应考虑的两个核心问题:做什么(WHAT)和怎么做(HOW)。文章强调了解析需求时的共性问题,包括关注UI组件数量、数据来源、数据与UI的关联、用户行为响应、用户行为采集以及发布后的运维和监控。作者通过实例和抽象层次图说明了如何拆解和实现这些关注点,并提供了具体的操作方法和建议,以帮助开发和测试人员更好地理解和处理需求。
使用ScottPlot库在.NET WinForms中快速实现大型数据集的交互式显示
使用ScottPlot库在.NET WinForms中快速实现大型数据集的交互式显示
327 1
|
资源调度 数据可视化 数据处理
R语言改进的DCC-MGARCH:动态条件相关系数模型、BP检验分析股市数据
R语言改进的DCC-MGARCH:动态条件相关系数模型、BP检验分析股市数据
|
编解码 网络协议 网络性能优化
RTP/RTCP 协议讲解
RTP/RTCP 协议讲解
1724 0
|
供应链 架构师 双11
供应链业务架构设计概览(一)
供应链业务架构设计概览
2117 0
|
Python
python股票量化交易(9)---使用TA-Lib库实现股价走势对比图
python股票量化交易(9)---使用TA-Lib库实现股价走势对比图
1290 1
python股票量化交易(9)---使用TA-Lib库实现股价走势对比图