今天和打家讲一下打家劫舍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。
关键点：
-
确保子节点状态传递正确，尤其是“不偷当前节点”时，子节点可自由选择偷或不偷。
-
后序遍历确保先处理子节点再处理父节点。
