968. Binary Tree Cameras

Loading...LeetCode

• 二叉树题，基本就是BFS/DFS

• 需要确认camera的摆放，就是要明确父节点/子节点间摆放决策的关系，然后依序传递（top-down or bottom-up）

• 对每个节点来说，可能的状态有三种，这三种分别存在以自己为root的子树中【可能的最小摄像头摆放数】：

• 1. 自己没放camera，也没被监控

  2. 自己没放camera，被监控

  3. 自己放了camera（当然肯定也就被监控）

  这三种状态所对应的其左右子节点状态是不一样的。

• 父子节点每种状态的【可能的最小摄像头摆放数】都可以由对方各个状态的数字确认

• 叶子节点是状态传递的开端（即bottom-up），状态为(0, float('inf'), 1)

# 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:
    @functools.lru_cache()
    def minCameraCover(self, root: TreeNode) -> int:
        if not root: return 0
        if not root.left and not root.right:
            root.status = (0, 0x7fffffff, 1)
        elif root.left and not root.right:
            self.minCameraCover(root.left)
            ## 只有左子树
            # 状态1（不被监控） -> 左树被监控但没灯
            # 状态2（被监控但没灯） -> 左树有灯
            # 状态3（有灯） -> 不管左树有没灯，但要+1
            root.status = (root.left.status[1], root.left.status[2], min(root.left.status)+1)
        elif root.right and not root.left:
            ## 只有右子树，类似上面
            self.minCameraCover(root.right)
            root.status = (root.right.status[1], root.right.status[2], min(root.right.status)+1)
        else:
            ## 左右都有
            self.minCameraCover(root.left)
            self.minCameraCover(root.right)
            # 状态1（不被监控） -> 左右都没灯
            root_unwatched = root.left.status[1] + root.right.status[1]
            # 状态2（被监控但没灯） -> min of [左树有灯+不管右树有没灯，右树有灯+不管左树有没灯]
            root_no = min([root.left.status[2]+min(root.right.status[1:]), root.right.status[2]+min(root.left.status[1:])])
            # 状态3（有灯） -> 不管左右树有没灯，但要+1
            root_put = min(root.left.status) + min(root.right.status) + 1
            root.status = (root_unwatched, root_no, root_put)
        return min(root.status[1:])