监控二叉树

题解采用了递归的方法，利用后序遍历（先处理子节点，再处理当前节点）的方式来决定在哪些节点上安装摄像头。递归函数返回三种状态：0 表示当前节点未被覆盖，1 表示当前节点已安装摄像头，2 表示当前节点已被覆盖但未安装摄像头。根据子节点的状态来决定当前节点的操作： 1. 如果任一子节点未被覆盖（返回0），则在当前节点安装摄像头，并返回状态1。 2. 如果所有子节点都已被覆盖（返回2），则当前节点返回状态0。 3. 如果任一子节点安装了摄像头（返回1），则当前节点返回状态2，表示已被覆盖。 最后，若根节点在递归后仍未被覆盖，则在根节点额外安装一个摄像头。

时间复杂度: O(n)

空间复杂度: O(n) in the worst case, O(log(n)) in the best case

# 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: TreeNode) -> int:
        result = [0]  # This list will store the number of cameras needed
        if self.traversal(root, result) == 0:  # If root is not covered
            result[0] += 1  # Place a camera at the root
        return result[0]

    def traversal(self, cur: TreeNode, result: list[int]) -> int:
        if not cur:  # If current node is None, it's considered covered
            return 2

        left = self.traversal(cur.left, result)
        right = self.traversal(cur.right, result)

        if left == 2 and right == 2:  # If both children are covered
            return 0  # Current node is not covered

        elif left == 0 or right == 0:  # If any child is not covered
            result[0] += 1  # Place a camera at the current node
            return 1  # Current node has a camera

        else:  # If at least one child has a camera or both are covered
            return 2  # Current node is covered