968监控二叉树

  • Z时代
  • 2024-01-10
  • 分类：综合

python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
a = TreeNode(0)
b = TreeNode(0)
c = TreeNode(0)
d = TreeNode(0)
a.left = b
b.left = c
b.right = d
# 对于子节点来说，我们可以把他定义为三种状态：
# 状态0：没有被监控。
# 状态1：被监控，且放置了相机
# 状态2：被监控，但是没有放置相机。
# 对于父节点来说，也是三种状态
# 子节点其中一个为0，父节点为1
# 子节点其中一个为1，父节点为2
# 子节点都为2，父节点要为0
class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        # 首先判断根节点不能为0
        if not root:
            return 0
        # 这里需要判断根节点的状态，如果根节点状态为0，需要在他这里放置一个相机
        count,status = self.dfs(root)
        if status == 0:
            count += 1
        return count
    def dfs(self,root):
        # 注意这里是None的时候需要放回2，被监控， 但是没有放置相机。
        if not root:
            return 0,2
        # 接收返回的相机数和状态。
        left_count,left_status = self.dfs(root.left)
        right_count,right_status = self.dfs(root.right)
        count = left_count + right_count
        # 如果子节点都为0，表示都没有被监控，那么父节点需要放置相机。
        if left_status == 0 or right_status == 0:
            return count + 1,1
        # 经历上边的if语句，下边只剩下了。11,12,21,22
        # 因此这时如果两个子节点其中一个为1的话就可以保证父节点为2了。
        elif left_status == 1 or right_status == 1:
            return count,2
        # 最后这里两个子节点都被监控，那么父节点就不被监控了。
        elif left_status == 2 and right_status == 2:
            return count,0
A = Solution()
print(A.minCameraCover(a))

以上是 968监控二叉树 的全部内容， 来源链接： utcz.com/z/529931.html

回到顶部