leetcode动态规划（二十三）-打家劫舍III

题目

337.打家劫舍III

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

思路

本题是将动态规划和二叉树结合在一起的题目，需要使用动态规划和二叉树的方法一起来解决

以递归三部曲穿插动规五步曲来进行分析

1.确定递归函数参数和返回值

参数即是传入的根节点

返回值这里选择返回选择偷当前节点的和不偷当前节点两种状态的结果

则dp数组即为返回值为：dp[0]偷当前节点能够得到的最高金额，dp[1]不偷当前节点能够得到的最高金额

2.确定终止条件

当节点为空的时候，就返回dp=[0,0]

3.确定遍历顺序

首先明确的是使用后序遍历。 因为要通过递归函数的返回值来做下一步计算。

通过递归左节点，得到左节点偷与不偷的金钱。

通过递归右节点，得到右节点偷与不偷的金钱。

4.确定单层递归的逻辑

如果是偷当前节点，那么左右孩子就不能偷，val1 = cur.val + left[1] + right[1]; （如果对下标含义不理解就再回顾一下dp数组的含义）

如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

5.举例dp数组

代码

# 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:
        dp = self.travel(root)
        return max(dp)


    def travel(self,cur):
        if not cur:
            return (0,0)

        left = self.travel(cur.left)
        right = self.travel(cur.right)

        #偷当前节点
        val1 = cur.val+left[1]+right[1]

        #不偷当前节点
        val2 = max(left)+max(right)

        return (val1,val2)