You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.
Return the minimum number of cameras needed to monitor all nodes of the tree.
Example 1:
Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.
Example 2:
Input: root = [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.
Constraints:
The number of nodes in the tree is in the range [1, 1000].
Node.val == 0
Solutions
Solution 1
1 2 3 4 5 6 7 8 91011121314151617181920
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defminCameraCover(self,root:Optional[TreeNode])->int:defdfs(root):ifrootisNone:returninf,0,0la,lb,lc=dfs(root.left)ra,rb,rc=dfs(root.right)a=min(la,lb,lc)+min(ra,rb,rc)+1b=min(la+rb,lb+ra,la+ra)c=lb+rbreturna,b,ca,b,_=dfs(root)returnmin(a,b)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcminCameraCover(root*TreeNode)int{vardfsfunc(*TreeNode)(int,int,int)dfs=func(root*TreeNode)(int,int,int){ifroot==nil{return1<<29,0,0}la,lb,lc:=dfs(root.Left)ra,rb,rc:=dfs(root.Right)a:=1+min(la,min(lb,lc))+min(ra,min(rb,rc))b:=min(la+ra,min(la+rb,lb+ra))c:=lb+rbreturna,b,c}a,b,_:=dfs(root)returnmin(a,b)}