day169—递归—打家劫舍Ⅲ（LeetCode-337）

题目描述

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为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

提示：

• 树的节点数在[1, 104]范围内
• 0 <= Node.val <= 104

解决方案：

这段代码是基于后序遍历（DFS）求解二叉树打家劫舍问题的核心实现，核心思路是通过递归记录每个节点 “选” 或 “不选” 时的最大收益，最终取整棵树根节点两种状态的最大值，得到能抢劫的最大金额。

核心逻辑

1. 核心定义：

   • dfs(root)：递归函数，返回长度为 2 的数组{root_is_val, root_no_val}：
     • root_is_val：选择抢劫当前节点时，以该节点为根的子树能获得的最大收益；
     • root_no_val：不选择抢劫当前节点时，以该节点为根的子树能获得的最大收益；
   • max_vector：辅助函数，返回数组中两个元素的最大值（替代原生max，逻辑等价）。

2. 递归边界：若root为空（!root），返回{0,0}—— 空节点无论选或不选，收益均为 0。

3. 后序遍历核心逻辑：

   • 先递归计算左子节点的 “选 / 不选” 收益left_val = dfs(root->left)；
   • 再递归计算右子节点的 “选 / 不选” 收益right_val = dfs(root->right)；
   • 计算当前节点 “选” 的收益：root_is_val = left_val[1] + right_val[1] + root->val（选当前节点则左右子节点都不能选，取子节点 “不选” 的收益之和 + 当前节点值）；
   • 计算当前节点 “不选” 的收益：root_no_val = max(left_val[0], left_val[1]) + max(right_val[0], right_val[1])（不选当前节点则左右子节点可选可不选，取各自两种状态的最大值之和）；
   • 返回当前节点的 “选 / 不选” 收益数组，供父节点计算。

4. 主函数逻辑：调用dfs(root)得到根节点的 “选 / 不选” 收益数组，通过max_vector取两者最大值，即为整棵树能抢劫的最大金额。

关键特点

• 时间复杂度 O (n)：每个节点仅被递归访问一次，n 为节点数；
• 空间复杂度 O (h)：h 为树的高度，递归栈深度等于树高，返回的数组仅占用常数空间；
• 状态定义清晰：通过 “选 / 不选” 两个状态拆分问题，符合 “打家劫舍” 的核心规则（不能抢劫相邻节点）；
• 逻辑自洽：选当前节点则子节点必不选，不选当前节点则子节点可选最优状态，完全贴合问题约束。

验证示例（简单二叉树）

假设有如下二叉树：

plaintext

3 / \ 2 3 \ \ 3 1

• 递归到叶子节点 3（左子树）：left_val={3,0}，叶子节点 1（右子树）：right_val={1,0}；
• 节点 2（左子节点）：选则收益 = 0+0+2=2，不选则收益 = 0+0=0 → 返回 {2,0}；
• 节点 3（右子节点）：选则收益 = 0+0+3=3，不选则收益 = 0+0=0 → 返回 {3,0}；
• 根节点 3：选则收益 = 0（左不选）+0（右不选）+3=3，不选则收益 = max (2,0)+max (3,0)=5 → 最终返回 max (3,5)=5（正确结果）。

总结

1. 核心思路：通过后序遍历递归记录每个节点 “选 / 不选” 的最大收益，利用状态转移规则（选则子节点不选，不选则子节点选最优）拆分问题；
2. 关键设计：用二维数组承载 “选 / 不选” 状态是核心，后序遍历确保先计算子节点再计算父节点；
3. 功能效果：能正确计算二叉树打家劫舍的最大收益，完全贴合 “不能抢劫相邻节点” 的规则约束。

函数源码：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int max_vector(vector<int> nums){ return nums[0]>nums[1]? nums[0]:nums[1]; } vector<int> dfs(TreeNode* root){ if(!root) return {0,0}; vector<int> left_val = dfs(root->left); vector<int> right_val=dfs(root->right); int root_is_val= left_val[1]+right_val[1]+root->val; int root_no_val= max(left_val[0],left_val[1])+max(right_val[0],right_val[1]); return {root_is_val,root_no_val}; } int rob(TreeNode* root) { //return max(dfs(root)[0],dfs(root)[1]); return max_vector(dfs(root)); } };