<p>You are given the <code>root</code> of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.</p>

<p>Return <em>the minimum number of cameras needed to monitor all nodes of the tree</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/29/bst_cameras_01.png" style="width: 138px; height: 163px;" />
<pre>
<strong>Input:</strong> root = [0,0,null,0,0]
<strong>Output:</strong> 1
<strong>Explanation:</strong> One camera is enough to monitor all nodes if placed as shown.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/29/bst_cameras_02.png" style="width: 139px; height: 312px;" />
<pre>
<strong>Input:</strong> root = [0,0,null,0,null,0,null,null,0]
<strong>Output:</strong> 2
<strong>Explanation:</strong> At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 1000]</code>.</li>
	<li><code>Node.val == 0</code></li>
</ul>

# 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

#2023/05/27
# class Solution:
#     def minCameraCover(self, root: Optional[TreeNode]) -> int:
#         self.res=0
#         def postOrder(node):
#             if node==None:
#                 return 2
#             left=postOrder(node.left)
#             right=postOrder(node.right)
#             if left==2 and right==2:
#                 return 0
#             if left==0 or right==0:
#                 self.res+=1
#                 return 1
#             if left==1 or right==1:
#                 return 2
#         if postOrder(root)==0:
#             self.res+=1
#         return self.res

#2024/06/04
'''
因为头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量 是指数阶别的。
所以我们要从下往上看，局部最优:让叶子节点的父节点安摄像头，所用摄像头最少，整体
最优:全部摄像头数量所用最少!

大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄
像头，直至到二叉树头结点。

所以需要一个办法去传递每个节点的状态

我们分别有三个数字来表示:
0:该节点无覆盖 1:本节点有摄像头 2:本节点有覆盖

如果左右哪怕只有一个是0，那必然本节点要放置，本节点状态变为1
如果左右都是2，那么本节点是没有覆盖的，应该要返回0
如果左右哪怕只有一个是1，本节点都是2

叶子节点不要放，所以叶子节点的左右应该返回2
'''
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        self.res=0
        def postorder(node):
            if node==None:
                return 0
            left=postorder(node.left)
            right=postorder(node.right)
            if left==2 and right==2:
                return 0
            #必须要0在1前面，因为一个0一个1，是应该放的
            if left==0 or right==0:
                self.res+=1
                return 1
            if left==1 or right==1:
                return 2
        #如果当前没有被覆盖
        if postorder(root)==0:
            self.res+=1
        return self.res


#2024/09/17
'''
一个node可以监视上下三个
到root要多少个取决于之前要多少个，所以dp
每个node有两种状态，放和不放
用dfs传递上来


不对，每个叶子节点有三个状态：
0：无覆盖
1：该叶子节点放了
2：该叶子节点没有房但是有覆盖

这个状态是可以传递的，所以dfs的过程中去更新每个Node的状态
如果该状态是0，那么就应该加1

为了让尽可能少放，叶子节点统一不放，所以叶子节点的左右必须返回2，这样叶子才能不放，且叶子的上一个必须放
'''
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        self.res=0
        def helper(root):
            if root==None:
                return 2
            left=helper(root.left)
            right=helper(root.right)
            if left==2 and right==2:
                return 0
            if left==0 or right==0:
                self.res+=1
                return 1
            if left==1 or right==1:
                return 2
        if helper(root)==0:
            self.res+=1
        return self.res            
17000