LeetCode337小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为root。除了root之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫房屋将自动报警。给定二叉树的root。返回在不触动警报的情况下小偷能够盗取的最高金额。示例输入:root [3,2,3,null,3,null,1]输出:7解释:小偷一晚能够盗取的最高金额 3 3 1 7Python解法动态规划# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def rob(self, root: Optional[TreeNode]) - int: def dfs(node: Optional[TreeNode]) - (int, int): if node is None: return 0, 0 l_rob, l_not_rob dfs(node.left) r_rob, r_not_rob dfs(node.right) rob node.val l_not_rob r_not_rob not_rob max(l_rob, l_not_rob) max(r_rob, r_not_rob) return rob, not_rob rob, not_rob dfs(root) return max(rob, not_rob)Java解法动态规划/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public int rob(TreeNode root) { int[] res dfs(root); return Math.max(res[0], res[1]); } private int[] dfs(TreeNode node){ if(node null){ return new int[]{0, 0}; } int[] left dfs(node.left); int[] right dfs(node.right); int rob node.val left[1] right[1]; int not_rob Math.max(left[0], left[1]) Math.max(right[0], right[1]); return new int[]{rob, not_rob}; } }C解法动态规划/** * 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: // pair选当前节点, 不选当前节点 pairint, int dfs(TreeNode* node) { if (!node) { return {0, 0}; } auto left dfs(node-left); auto right dfs(node-right); int rob node-val left.second right.second; int notRob max(left.first, left.second) max(right.first, right.second); return {rob, notRob}; } int rob(TreeNode* root) { auto [r, nr] dfs(root); return max(r, nr); } };解释原理一、题目核心约束二叉树结构房屋不能同时选取直接相连的父子节点求能偷窃的最大金额。通俗规则选了父节点左右子节点一定不能选不选父节点子节点自由决策。二、树上动态规划核心思想普通一维打家劫舍是线性 DP本题是树形 DP。 树形 DP 通用特征父节点最优解依赖子节点的最优解因此采用后序遍历先算出左右子树结果再计算当前节点。状态定义最关键对任意节点node定义两种状态二选一覆盖所有方案{rob})打劫当前节点node以 node 为根的子树能拿到的最大收益{not_rob})不打劫当前节点node以 node 为根的子树能拿到的最大收益为什么必须维护两个状态 如果只保存 “子树最大收益” 单一数值无法记录「子节点是否被选取」。当父节点选择打劫时我们需要知道子节点不能选情况下的收益单一值信息不足。
