这道题目是 打家劫舍 III（House Robber III），是打家劫舍系列问题的变种。问题描述如下：
小偷发现了一个新的区域，这个区域的所有房屋排列类似于一棵二叉树。如果两个直接相连的房屋在同一晚被打劫，房屋会自动报警。给定这棵二叉树的根节点
root，求在不触发警报的情况下，小偷能够盗取的最高金额。
题目思路
1. 问题分析
- 每个节点（房屋）有两个状态：偷 或 不偷。
- 如果偷了当前节点，则不能偷其直接子节点（左子节点和右子节点）。
- 如果不偷当前节点，则可以偷其子节点，也可以选择不偷子节点。
- 目标是找到一种偷窃方案，使得总金额最大。
2. 解题方法
这道题有两种常见的解法：
- 记忆化搜索 + 递归
- 树形动态规划（树形DP）
不能用层序遍历化为一维数组再套用前面的打家劫舍。如以下情况不能解决
方法一：记忆化搜索 + 递归
思路
- 对于每个节点，有两种选择：
- 偷当前节点：不能偷其左右子节点，但可以偷其孙子节点（左右子节点的子节点）。
- 不偷当前节点：可以考虑偷其左右子节点。
- 使用递归计算这两种选择的最大值。
- 记忆化搜索：每次偷爷爷节点时，又要重新计算孙子节点。但在此之前孙子节点已经计算过了。为了避免重复计算，使用
unordered_map<TreeNode*, int>进行记忆化存储。
之前记忆化搜索一般使用数组（如斐波那契数列）缓存。但二叉树不适合拿数组当缓存，我们这次使用哈希表来存储结果
代码实现
class Solution {
public:
unordered_map<TreeNode*, int> mp; // 记忆化存储
int rob(TreeNode* root) {
if (root == nullptr) return 0; // 空节点，返回0
if (mp[root]) return mp[root]; // 如果已经计算过，直接返回
// 偷当前节点
int val1 = root->val;
if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 偷孙子节点
if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 偷孙子节点
// 不偷当前节点
int val2 = rob(root->left) + rob(root->right); // 偷子节点
mp[root] = max(val1, val2); // 记录当前节点的最大值
return mp[root];
}
};
复杂度分析
- 时间复杂度：
O(n)，其中n是节点数量。每个节点只会被计算一次。 - 空间复杂度：
O(n)，用于存储记忆化结果和递归栈。
方法二：树形动态规划（树形DP）
方法一还要考虑孙子节点，能不能只考虑儿子——>记录每个节点选/不选的状态最大值
思路
- 对于每个节点，返回一个长度为 2 的数组
dp：dp[0]：不偷当前节点时的最大金额。dp[1]：偷当前节点时的最大金额。
- 通过后序遍历（左右根）计算每个节点的
dp值。 - 最终结果是根节点的
dp[0]和dp[1]的最大值。
代码实现
- 树形DP在树上进行状态转移，因此需要递归实现
class Solution {
public:
int rob(TreeNode* root) {
vector<int> result = robTree(root);
return max(result[0], result[1]); // 返回偷或不偷根节点的最大值
}
vector<int> robTree(TreeNode* root) {
if (root == nullptr) return {0, 0}; // 空节点，返回 {0, 0}
vector<int> left = robTree(root->left); // 左子树的 dp 值
vector<int> right = robTree(root->right); // 右子树的 dp 值
// 不偷当前节点：左右子树可偷可不偷
int val0 = max(left[0], left[1]) + max(right[0], right[1]);
// 偷当前节点：左右子树不可偷
int val1 = root->val + left[0] + right[0];
return {val0, val1}; // 返回当前节点的 dp 值
}
};
复杂度分析
- 时间复杂度：
O(n)，每个节点只会被访问一次。 - 空间复杂度：
O(n)，递归栈的深度最大为树的高度。
方法对比
| 方法 | 优点 | 缺点 |
|---|---|---|
| 记忆化搜索 + 递归 | 直观，易于理解 | 需要额外的空间存储记忆化结果 |
| 树形DP | 空间效率更高，无需额外存储 | 需要理解状态转移方程 |
总结
- 记忆化搜索 + 递归：通过递归遍历树，同时使用
unordered_map存储中间结果，避免重复计算。 - 树形DP：通过后序遍历，返回每个节点的状态值（偷或不偷），最终选择最大值。
两种方法的时间复杂度都是 O(n)，但树形DP的空间效率更高，推荐使用树形DP。