当前位置：首页 > news >正文

打家劫舍3

news 2025/6/29 2:17:38

今天和打家讲一下打家劫舍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)）。