天水地区建网站,dede网站后台导入文档,成都网站开发培训,excel做网站链接今天和打家讲一下打家劫舍3 题目#xff1a;
题目链接#xff1a;337. 打家劫舍 III - 力扣#xff08;LeetCode#xff09; 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口#xff0c;我们称之为root。 除了 root 之外#xff0c;每栋房子有且只有一个“父“… 今天和打家讲一下打家劫舍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 pairint,int PII;
public:int rob(TreeNode* root) {if(!root) return 0;auto t dfs(root);int ansmax(t.x,t.y);return ans;}inline PII dfs(TreeNode* u){//pairtou,butouif(!u) return {0,0};int stolenu-val;PII l dfs(u-left);PII r dfs(u-right);stolen l.yr.y ;int nostolen0;if (l.xl.y) nostolenl.x;else nostolen l.y;if (r.xr.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 pairint, int PII;
PII 是一个二元组存储两个状态
firstx偷当前节点时的最大收益。
secondy不偷当前节点时的最大收益。
主函数 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 时的最大收益。
状态转移
偷当前节点 不能偷子节点因此收益为
stolenu.valleft.yright.ystolenu.valleft.yright.y
不偷当前节点 子节点可自由选择偷或不偷取最大值相加
nostolenmax(left.x,left.y)max(right.x,right.y)nostolenmax(left.x,left.y)max(right.x,right.y)
递归过程 从叶子节点向上递推确保每个节点的状态仅依赖子节点的状态。 示例分析:
假设二叉树如下 3/ \2 3\ \ 3 1 叶子节点值为3和1的节点
stolen 3或1nostolen 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。 关键点 确保子节点状态传递正确尤其是“不偷当前节点”时子节点可自由选择偷或不偷。 后序遍历确保先处理子节点再处理父节点。
