968监控二叉树[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))
hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » 968监控二叉树