树形DP学习笔记（二）：打家劫舍III & 监控二叉树

参考：

树形 DP：打家劫舍III【基础算法精讲 24】_哔哩哔哩_bilibili

树形 DP：监控二叉树【基础算法精讲 25】_哔哩哔哩_bilibili

ps：笔记中的代码按本人理解整理，重思路，对比原视频中的代码稍有改动

往期：

树形DP学习笔记（一）：树的路径问题-CSDN博客

状态机DP学习笔记-CSDN博客

【如果笔记对你有帮助，欢迎关注&点赞&收藏，收到正反馈会加快更新！谢谢支持！】

上期树的每个节点只传递一个值（如深度、对应数值等）

这期树的每个节点需要传递多个值（每个节点有多种可能情况，需要分类讨论）

但是核心思路不变

题目4: 打家劫舍III

337. 打家劫舍 III - 力扣（LeetCode）

• 思路：每个节点有偷和不偷两种情况，对应的金额都需要传递（因为都需要用到，传递的是这棵树的金额）
• 拆解：
  • 偷当前节点：左节点不偷，右节点不偷
    【树的金额 = 当前节点金额 + 不偷左节点时左子树的金额 + 不偷右节点时右子树的金额】
  • 不偷当前节点：左节点偷/不偷都可以，右节点偷/不偷都可以
    【树的金额 = 左子树金额即max{偷左节点时，不偷左节点时}+ 右子树金额即max{偷右节点时，不偷右节点时}】
• 代码

  # 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 dfs(self, root: Optional[TreeNode]):
          if not root:
              return (0,0) # 节点为None，返回0，确定递归边界
  
          # w表示偷，wo表示不偷
          # 左右节点都需要传递回这两种情况对应的金额，给当前节点使用【这里root指当前节点，不是树的根节点】
          w_l, wo_l = self.dfs(root.left) # 返回左节点选择偷和选择不偷时左子树的金额
          w_r, wo_r = self.dfs(root.right) # 返回右节点选择偷和选择不偷时右子树的金额
          # 当前节点处理
          # 偷当前节点：当前节点金额 + 不偷左节点时，左子树的金额 + 不偷右节点时，右子树的金额
          # 不偷当前节点：左子树金额（偷或不偷左节点情况哪个大取哪个）+ 右子树金额（偷或不偷右节点情况哪个大取哪个）
          w_root = wo_l + wo_r + root.val 
          wo_root = max(w_l, wo_l) + max(w_r, wo_r)
          return (w_root, wo_root)
  
      def rob(self, root: Optional[TreeNode]) -> int:
          return max(self.dfs(root)) # 偷root和不偷root的情况哪个大取哪个
  
        
  

题目5: 监控二叉树

968. 监控二叉树 - 力扣（LeetCode）

• 变化：【考虑单元】 “当前节点，左节点，右节点”  → “当前节点，父节点，左节点，右节点”

  

• 思路：当前节点要监控到有三种办法（如下），所对应的数量都要传递
• 拆解：
  • 要保证当前节点被监控到，有三个方法：
    1. 当前节点装摄像头。 数量 = 左值 + 右值 + 1
    2. 当前节点不装摄像头，其父节点装。数量 = 左值 + 右值
    3. 当前节点不装摄像头，其子节点装。数量 = 左值 + 右值
  • 更详细的解释版本：
    【这里要理解成“担保”，意思用下面哪个方法来“担保”当前节点是被监控的，而不是安装情况的分类讨论】
    1. 当前节点装摄像头【自己“担保”】：左节点的担保情况可以是（1）自己“担保” （2）靠父节点“担保” （3）靠子节点“担保”。右节点同理。 因为要求最小数量，所以要取所有情况的最小值。
    2. 当前节点不装摄像头，其父节点装【父节点“担保”】：左节点的担保情况可以是：（1）自己“担保”  （2）靠子节点“担保”。不能靠父节点担保了，因为父节点没装。右节点同理。
    3. 当前节点不装摄像头，其子节点装【子节点“担保”】：左节点和右节点必须有一个来担保。两种情况：
       1. 选左节点“担保”时， 右节点的担保情况可以是（1）自己”担保“ （2）子节点”担保“。
       2. 选右节点“担保”时， 左节点的担保情况可以是（1）自己”担保“ （2）子节点”担保“。
• 代码

• # 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 minCameraCover(self, root: Optional[TreeNode]) -> int:
          
          def dfs(root):  
              if not root:
                  return (float('inf'), 0, 0) #第一个要初始化为无穷大的原因写在最后，先看下面递归过程
              
              # r: 装当前节点(root)， p：装父节点(parent)， c装子节点(child) 【这里的root指代当前节点，不是根节点】
              # 左右节点都需要传递回这三种情况对应的数量，给当前节点使用
              r_left, p_left, c_left = dfs(root.left) 
              r_right, p_right, c_right = dfs(root.right)
  
              # 当前节点装摄像头【r】：左节点可以是（1）自己装【r_left】（2）靠父节点装【p_left】 （3）靠子节点装【c_left】。右节点同理。
              # 当前节点不装摄像头，其父节点装【p】：左节点可以是（1）自己装【r_left】(2)靠子节点装【c_left】。右节点同理。
              # 当前节点不装摄像头，其子节点装【r】：
              # 1.当靠左节点装【r_left】时，右节点可以是（1）自己装【r_right】(2)靠子节点装【c_right】
              # 2.当靠右节点装【r_right】时，左节点可以是（1）自己装【r_left】(2)靠子节点装【c_left】
              r = min(r_left, p_left, c_left) + min(r_right, p_right, c_right) + 1
              p = min(r_left, c_left) + min(r_right, c_right) 
              c = min(r_left + min(r_right, c_right), r_right + min(r_left, c_left))
  
              return r, p ,c
          
          # 因为根节点没有父节点，所以返回的父节点情况不能用，
          # 但也是可以返回值的，所以可以当作常规节点一起讨论，不用特殊处理
          r, _, c = dfs(root) 
          return min(r, c)
  
  
  ### 解释为什么初始化（当前节点为空）的时候，自己装的情况要返回无穷大 ###
  # 计算c = min(r_left + min(r_right, c_right), r_right + min(r_left, c_left))的时候
  # 左右节点为空，r_left = r_right = inf 时，r = 0, p = 0, c = inf，表示不存在用装子节点的情况（因为我们取min的时候不会取到c）
  # 如果装的情况也要返回0，那么c=0，就会取最小值就会取到c，但是子节点不存在，所以不能这样