337.打家劫舍III

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 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:
        # 这是一道二叉树 和 动态规划的 经典结合题，递归的过程没有发生在数组中，而是发生在二叉树的遍历过程中。
        # 思路：二叉树的每个节点中都存 偷和不偷两种 状态，用后序遍历由下往上收，最后汇聚到根节点，我们通过根节点中 两种状态的 值比较，选择出最优解的偷盗选项。
        # 每个节点偷还是不偷的 状态由两种情况决定，
        # 偷本节点，那“偷”状态的值在本节点 = 那两个子节点就不能偷，
        # 不偷本节点，那“不偷”状态的值在本节点 = 那左孩子随便偷不偷的最大值 + 右孩子随便偷不偷的最大值。
        # 实际的最优偷盗路线就是沿着最大化的方向往下走，但是我们只求金额。
        # 每个节点返回 1维的dp数组，【当前不偷(最大总金额数),当前偷(最大总金额数)】
        def robtree(root)->List[int]:
            if root==None:return [0,0]
            left_arr = robtree(root.left)
            right_arr = robtree(root.right)
            # 计算当前节点 偷和不偷的最大值;
            rob = root.val + left_arr[0] + right_arr[0]
            norob = max(left_arr[0],left_arr[1]) + max(right_arr[0],right_arr[1])
            return [ norob, rob ]            
        result = robtree(root)
        return max(result[0],result[1])