欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 财经 > 金融 > 打家劫舍3

打家劫舍3

2025/7/5 7:17:50 来源:https://blog.csdn.net/2301_81253185/article/details/145535210  浏览:    关键词:打家劫舍3

今天和打家讲一下打家劫舍3

题目:

题目链接:337. 打家劫舍 III - 力扣(LeetCode)

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为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

代码: 

class Solution {#define x first#define y second typedef pair<int,int> PII;
public:int rob(TreeNode* root) {if(!root) return 0;auto t =dfs(root);int ans=max(t.x,t.y);return ans;}inline  PII dfs(TreeNode* u){//pair<tou,butou>if(!u) return {0,0};int stolen=u->val;PII l = dfs(u->left);PII r = dfs(u->right);stolen +=l.y+r.y ;int nostolen=0;if (l.x>l.y)  nostolen=l.x;else nostolen =l.y;if (r.x>r.y)  nostolen +=r.x;else nostolen +=r.y;PII t={stolen , nostolen};return t;}
};

运行效率:

 

 宏定义与类型别名:

#define x first    // 用 x 表示 pair 的 first(偷当前节点的最大值)
#define y second   // 用 y 表示 pair 的 second(不偷当前节点的最大值)
typedef pair<int, int> PII;

PII 是一个二元组,存储两个状态:

first(x):偷当前节点时的最大收益。
second(y):不偷当前节点时的最大收益。

主函数 rob:

若树为空,直接返回0。

调用dfs递归计算根节点的两种状态,返回较大值。

int rob(TreeNode* root) {if (!root) return 0;auto t = dfs(root);return max(t.x, t.y); // 最终结果取根节点偷或不偷的最大值
}

递归函数 dfs:

PII dfs(TreeNode* u) {if (!u) return {0, 0}; // 空节点返回 {0,0}int stolen = u->val;   // 偷当前节点PII l = dfs(u->left);  // 递归左子树PII r = dfs(u->right); // 递归右子树stolen += l.y + r.y;   // 偷当前节点时,左右子节点必须不偷// 不偷当前节点时,左右子节点可偷或不偷(取各自最大值相加)int nostolen = max(l.x, l.y) + max(r.x, r.y); return {stolen, nostolen}; // 返回当前节点的两种状态
}
  • 偷当前节点(stolen):
    当前节点的值 + 左子节点不偷的最大值(l.y) + 右子节点不偷的最大值(r.y)。

  • 不偷当前节点(nostolen):
    左子节点偷或不偷的最大值(max(l.x, l.y)) + 右子节点偷或不偷的最大值(max(r.x, r.y))。


动态规划逻辑:

状态定义:

代码通过后序遍历 + 动态规划实现,每个节点返回两个状态:

  • stolen(偷当前节点的最大收益)
  • not_stolen(不偷当前节点的最大收益)
    最终取根节点的两种状态的最大值。

对每个节点 u,定义两个状态:

stolen(偷 u 时的最大收益)。

nostolen(不偷 u 时的最大收益)。

状态转移:

偷当前节点
不能偷子节点,因此收益为:

stolen=u.val+left.y+right.ystolen=u.val+left.y+right.y

不偷当前节点
子节点可自由选择偷或不偷,取最大值相加:

nostolen=max⁡(left.x,left.y)+max⁡(right.x,right.y)nostolen=max(left.x,left.y)+max(right.x,right.y)

递归过程:

  • 从叶子节点向上递推,确保每个节点的状态仅依赖子节点的状态。


示例分析:

假设二叉树如下:

     3/ \2   3\   \ 3   1

叶子节点(值为3和1的节点):

  • stolen = 3(或1),nostolen = 0(不偷叶子节点时无收益)。

中间节点(值为2的节点):

  • 偷:2 + 0(左子不偷) + 0(右子不偷) = 2。
  • 不偷:max(0, 3)(左子偷或不偷的最大值) + 0 = 3。

根节点(值为3):

  • 偷:3 + 3(左子不偷) + 1(右子不偷) = 7。
  • 不偷:max(2, 3)(左子状态) + max(3, 1)(右子状态) = 3 + 3 = 6。

最终结果:max(7, 6) = 7。

关键点:

  • 确保子节点状态传递正确,尤其是“不偷当前节点”时,子节点可自由选择偷或不偷。

  • 后序遍历确保先处理子节点再处理父节点。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词