打家劫舍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。

关键点：

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

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