class TreeNode:<br> def __init__(<a href="https://www.gaodaima.com/tag/self" title="查看更多关于self的文章" target="_blank">self</a>, x):<br> self.val = x<br> self.left = None<br> self.right = None<br>a = TreeNode(0)<br>b = TreeNode(0)<br>c = TreeNode(0)<br>d = TreeNode(0)<br>a.left = b<br>b.left = c<br>b.right = d<br># 对于子<a href="https://www.gaodaima.com/tag/%e8%8a%82%e7%82%b9" title="查看更多关于节点的文章" target="_blank">节点</a>来说，我们可以把他定义为三种状态：<br># 状态0：没有被监控。<br># 状态1：被监控，且放置了相机<br># 状态2：被监控，但是没有放置相机。<br># 对于父节点来说，也是三种状态<br># 子节点其中一个为0，父节点为1<br># 子节点其中一个为1，父节点为2<br># 子节点都为2，父节点要为0<br>class Solution:<br> def minCameraCover(self, root: TreeNode) -> int:<br> # 首先判断根节点不能为0<br> if not root:<br> return 0<br> # 这里需要判断根节点的状态，如果根节点状态为0，需要在他这里放置一个相机<br> count,status = self.dfs(root)<br> if status == 0:<br> count += 1<br> return count<br> def dfs(self,root):<br> # 注意这里是None的时候需要放回2，被监控， 但是没有放置相机。<br> if not root:<br> return 0,2<br> # 接收返回的相机数和状态。<br> left_count,left_status = self.dfs(root.left)<br> right_count,right_status = self.dfs(root.right)<br> count = left_count + right_count<br> # 如果子节点都为0，表示都没有被监控，那么父节点需要放置相机。<br> if left_status == 0 or right_status == 0:<br> return count + 1,1<br> # 经历上边的if语句，下边只剩下了。11,12,21,22<br> # 因此这时如果两个子节点其中一个为1的话就可以保证父节点为2了。<br> elif left_status == 1 or right_status == 1:<br> return count,2<br> # 最后这里两个子节点都被监控，那么父节点就不被监控了。<br> elif left_status == 2 and right_status == 2:<br> return count,0<br>A = Solution()<br>print(A.minCameraCover(a))
www#gaodaima.com来源gao!%daima.com搞$代*!码$网搞代码
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：968监控二叉树
转载请注明原文链接：968监控二叉树
