Given a binary tree, we install cameras on the nodes of the tree.
Each camera at a node can monitorits parent, itself, and its immediate children.
Calculate the minimum number of cameras needed to monitor all nodes of the tree.
Example 1:
Input:
[0,0,null,0,0]
Output:
1
Explanation:
One camera is enough to monitor all nodes if placed as shown.
Example 2:
Input:
[0,0,null,0,null,0,null,null,0]
Output:
2
Explanation:
At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.
Note:
The number of nodes in the given tree will be in the range [1, 1000].
Every node has value 0.
分析
3个状态NOT_MONITORED = 0
MONITORED\_NOCAM = 1
MONITORED\_WITHCAM = 2
尽量往上放
1 2个儿子都被监视，求助parent
2任意儿子不被监视，本地放置 res++
3 直接返回被监视（可能儿子处放置
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def minCameraCover(self, root: TreeNode) -> int:
NOT_MONITORED = 0
MONITORED_NOCAM = 1
MONITORED_WITHCAM = 2
cameras = 0
if not root:
return 0
def dfs(root: TreeNode) -> int:
nonlocal cameras
if not root:
return MONITORED_NOCAM
left = dfs(root.left)
right = dfs(root.right)
if left == MONITORED_NOCAM and right ==MONITORED_NOCAM:
return NOT_MONITORED
elif left == NOT_MONITORED or right == NOT_MONITORED:
cameras += 1
return MONITORED_WITHCAM
else:
return MONITORED_NOCAM
top = dfs(root)
return cameras+1 if top== NOT_MONITORED else cameras
