首页 > 试题广场 >

打家劫舍(三)

[编程题]打家劫舍(三)
  • 热度指数:1835 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。
问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动警报的情况下同时偷窃两个相邻的房间,在不触动警报的情况下最多的偷窃金额。

1.如果输入的二叉树为{2,1,2,#,2,#,1},那么形状结构如下:


小区入口的房间的值是2 ,偷窃第一层2和第三层 2,1 是最优方案。




2.如果输入的二叉树为{3,2,10},那么形状结构如下:

样例2:小区入口的房间的值是3 ,偷窃第二层 2,10 是最优方案。

数据范围:二叉树节点数量满足 ,树上的值满足
示例1

输入

{2,1,2,#,2,#,1}

输出

5
示例2

输入

{3,2,10}

输出

12
示例3

输入

{3,5,#,10}

输出

13

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
头像 xqxls
发表于 2022-03-04 23:13:17
题意整理 给定一个二叉树结构的小区,每个节点都有一个房子。 现在有一个小偷,想偷到尽可能多的现金,但是不能偷相邻的房间,问最多偷多少现金。 方法一(递归) 1.解题思路 递归终止条件:遍历完所有节点。 递归如何传递:分别计算选与不选当前节点的情况。如果选,则加上当前节点、左孩子对应的孙子的情况 展开全文
头像 AimerAimer
发表于 2022-02-04 10:56:14
题意:         给定一棵二叉树,不能偷窃相邻的节点,问最大偷窃金额是多少?         方法一: 动态规划 展开全文
头像 CroMarmot
发表于 2022-02-21 16:59:15
打家劫舍(三) 题意 给定一个数字二叉树,不能选相邻的两个节点,问选的数的最大的和是多大 方法 深搜(TLE) 分析 我们递归搜索,每次递归时传递当前位置是否可选 如果不选这个位置,那么下一层递归的点都是可选 如果可选且选定这个位置,那么下一层递归的值都不可选 在递归过程中记录选择的和 最后输出和中 展开全文
头像 超级大米
发表于 2021-12-06 20:11:01
针对每个节点,有两种情况,选,或者不选,而该点的最大值为可以分为两种情况,选择该点时和不选择该点时,如果不选择该点,只需要获得左右子节点的最大值并相加,如果需要选择点,则需要获左右子节点都不直接选择的最大值(所以每次递归需要把子节点不选择时的最大值也返回上来)。最后比较两种情况的大小返回真正的最大值 展开全文
头像 不愿吃饼的土拨鼠很爱交友
发表于 2023-04-13 22:17:37
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullpt 展开全文
头像 牛客313925129号
发表于 2022-02-28 14:56:44
题意理解 相比于前面两题,这里把房子的布局设置为二叉树的形式。现在要求选择数字的时候,父结点和孩子结点不能同时选。 方法一 深度优先搜索 对于某个结点,可以选择或者不选,我们通过深度优先搜索遍历出每种可能的情况,并计算出对应结点数字的总和。如果选择当前结点,那么以它为根结点的数字总和为它本身加上以其 展开全文
头像 zcr214
发表于 2021-12-08 09:59:02
动态规划,单看一个二叉树结构,当前节点取得最大值分为偷或不偷两种情况,取决于左右两边是否偷了 每次计算返回当前节点偷和不偷分别能够取得的最大值 当前节点偷:则左右两边都不能偷,即: yes=no左+no右+当前值 当前节点不偷:则左右两边都偷了,或都不偷,或左右只有一个偷了,即: no=ma 展开全文
头像 认认真真coding
发表于 2022-02-23 19:24:10
打家劫舍(三) 题目描述 你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。 问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动 展开全文
头像 氯化钠哈哈哈
发表于 2024-05-22 15:28:12
好久没有一把过了本人语文水平不咋地,代码也写的不咋样欢迎大家的评判与指正总体思路: 自底向上的找出每个节点被打劫和不被打劫时,两种情况下的最大值 然后每个节点就可以根据自身的情况来找出,以当前节点为根节点时的最优解 当 当前节点被打劫时,两个子节点一定不会被打劫,则用当前节 展开全文

问题信息

难度:
8条回答 1775浏览

热门推荐

通过挑战的用户

查看代码