leetcode：968. Monitor the binary tree [tree DP, maintain the three states of each node's subtree, it is very difficult to think of the right as a learning, analogous to the house raiding 3]

analysis

Three states , Record the subtree with each node as the root ：
state a：root When the camera must be placed , The number of cameras needed to cover the entire tree .
state b： The number of cameras needed to cover the entire tree , No matter what root Whether to place the camera .
state c： Number of cameras required to cover two subtrees , Regardless of node root Whether it is monitored .
a >= b >= c

a = lc + rc + 1
b = min(a, la + rb, ra + lb)
c = min(a, lb + rb)

Formula 1： The current root has been placed , Just cover two subtrees （ Lower requirements ）
Formula 2： If you let it go root Namely a, If not, at least one of the left and right children will be released , Put it on the left and follow it on the right la + rb, Put right and follow left ra + lb
Formula 3： If you let it go root Namely a, If you don't put , That is, the possibility of two subtrees covering

If it's empty , Obviously, you can't choose , therefore a fill inf

ac code

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        #  Trees dp： Three states （ unimaginable ）
        #  state  a：root  When the camera must be placed , The number of cameras needed to cover the entire tree .
        #  state  b： The number of cameras needed to cover the entire tree , No matter what  root  Whether to place the camera .
        #  state  c： Number of cameras required to cover two subtrees , Regardless of node  root  Whether it is monitored .
        # a >= b >= c

        def dfs(root: TreeNode) -> List[int]:
            if not root:
                return [float("inf"), 0, 0] #  Impossible , use inf
            
            la, lb, lc = dfs(root.left)
            ra, rb, rc = dfs(root.right)
            a = lc + rc + 1
            b = min(a, la + rb, ra + lb)
            c = min(a, lb + rb)
            #print(a, b, c)
            return [a, b, c]
        
        a, b, c = dfs(root)
        return b

summary

Trees dp Board question
How to think of the three states ？ lament one 's littleness before the vast ocean ！