# 968. Binary Tree Cameras

{% embed url="<https://leetcode.com/problems/binary-tree-cameras/>" %}

* 二叉树题，基本就是BFS/DFS
* 需要确认camera的摆放，就是要明确父节点/子节点间摆放决策的关系，然后依序传递（top-down or bottom-up）
* 对每个节点来说，可能的状态有三种，这三种分别存在`以自己为root的子树中【可能的最小摄像头摆放数】`：
*

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

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

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

* 父子节点每种状态的`【可能的最小摄像头摆放数】`都可以由对方各个状态的数字确认
* 叶子节点是状态传递的开端（即bottom-up），状态为`(0, float('inf'), 1)`&#x20;

```python
# 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:])
```
