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))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/115023.html
標籤：Python