LeetCode 热题 HOT 100 （038/100）【宇宙最简单版】

【动态规划】No. 0337 打家劫舍III【中等】👉力扣对应题目指路

希望对你有帮助呀！！💜💜 如有更好理解的思路，欢迎大家留言补充 ~ 一起加油叭 💦
欢迎关注、订阅专栏 【力扣详解】谢谢你的支持！

⭐ 题目描述：小偷发现了一个可行窃的地区：除了入口 root 外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警

• 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额

• 示例 ：

  

  输入: root = [3,2,3,null,3,null,1]
  输出: 7
  解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

🔥 思路：后序遍历 + DP (当前节点对应的盗取的最高金额可能有两种情况)

• 偷：偷当前节点获取的 node.val + 不偷左孩子获取的最高金额 + 不偷右孩子获取的最高金额
• 不偷：不偷当前节点获取的 0 + 偷/不偷左孩子获取的最高金额 + 偷/不偷右孩子获取的最高金额

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def rob(self, root: Optional[TreeNode]) -> int:def robTree(node):  # 后序遍历，因为要用到左右孩子的结果if not node: return [0, 0]l_v = robTree(node.left)r_v = robTree(node.right)val_1 = node.val + l_v[1] + r_v[1]  # 偷   curval_2 = max(l_v) + max(r_v)         # 不偷 curreturn [val_1, val_2]return max(robTree(root))

希望对你有帮助呀！！💜💜 如有更好理解的思路，欢迎大家留言补充 ~ 一起加油叭 💦
🔥 LeetCode 热题 HOT 100