当前位置:网站首页>337. 打家劫舍 III
337. 打家劫舍 III
2022-08-09 03:54:00 【ZNineSun】
打卡!!!每日一题
今天给大家带来一道经典的动态规划题目:打家劫舍系列。
题目描述:337. 打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。
除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。
示例:
这道题,我们首先要找到一个突破口,如果我们从根节点来出发,那么到底要不要偷根节点,我们无从判断,因为其受制于子节点,所以我们需要找一个不受制于任何一个结点的结点来下手,很明显,叶子节点最适合不过了,因为从叶子开始,其后继结点为空。
同时我们用一个数组来保存每一个结点的盗窃情况[select,notSelect],即偷和不偷对应的金额。
如果想先遍历叶子节点,在遍历根节点,很明显后序遍历在合适不过了。
对于每个节点来说,都有两种情况:偷和不偷,我们只需要每次取最大值即可。
int[]left=dfs(root.left);
int[]right=dfs(root.right);
对于我们遍历到的结点,也是如此,也是偷和不偷两种可能
- 偷的话,那么对应的子节点只有不偷一种可能性,所以是l[1],r[1]
- 不偷的话,对于其子节点就没有限制了,可以偷也可以不偷,我们只需要做好判断,每个都确保是最大值即可。
int select = root.val + l[1] + r[1];//偷
int noSelect = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);//不偷
从上面这个过程我们也很容易看出,为何要采用后序遍历,因为根节点的状态完全依赖于其子节点。
完整代码如下:
public class 打家劫舍III_337 {
public int rob(TreeNode root) {
int[] money = dfs(root);
return Math.max(money[0], money[1]);
}
public int[] dfs(TreeNode root) {
if (root == null) {
return new int[]{
0, 0};
}
int[] l = dfs(root.left);
int[] r = dfs(root.right);
int select = root.val + l[1] + r[1];
int noSelect = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
return new int[]{
select, noSelect};
}
}
边栏推荐
猜你喜欢
随机推荐
宝塔实测-在线药店商城源码带WAP版
06 动态内存
NanoDet代码逐行精读与修改(一)Backbone
07.1 类的的补充
别跟客户扯细节
A few words about Microsoft's 2022/2023 autumn recruits
Linux安装MySQL8
关于微软2022/2023秋招内推的几句
leetcode 5722. 截断句子
光刻机随感
状态机使用小结
Polygon zkEVM Prover
phpStdudy的下载和DVWA的搭建
笔记本重装系统如何找回之前自己自带的office
leetcode 2021春季挑战赛 1. 采购方案
给电脑重装系统后修改远程桌面端口的方法
07.1 Supplements to the class
数据库指标是怎么个意思
发明时代,「幂集创新」事关你我
el-popover 内嵌 el-table 后位置错位 乱飘 解决方案