968. Binary Tree Cameras
Question
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.
Solution 1
贪心算法,后序遍历。每次递归根据下面两个子节点的状态来决定当前节点的状态。
每个节点一共有三种状态:
- 未被监控,返回0。
- 摄像头,返回1。
- 已被监控,返回2。
递归,当当前节点为空,则返回2,表示已被监控。这样叶子节点则为未被监控的状态。
如果下面的子节点有一个未被监控,则当前节点需要设置相机,返回1,计数res+1。
如果下面的子节点有一个为摄像头,则当前节点已被监控,返回2。
否则下面的节点均为已被监控,此时返回未被监控0。
Code
1 | /** |
Solution 2
参考:从递归优化到树形DP
树形DP。
递归,每次返回当前节点所有子节点的最小相机数。
每一个节点有三种状态:
- 放置了相机。
- 没有相机,但是被父节点parent监控。
- 没有相机,但是被子节点son监控。
将三种状态分别传入minCam()方法。
递归方法 minCam()
在递归时传入两个参数hasCamera和isWatched,来判断当前节点是否有相机,是否被监控。
当当前节点为空节点时,如果设置应当有相机(做不到)则返回无限大,消除这个返回值。如果不应该有相机,则返回0。
向下递归子节点。
- 当当前节点应该有相机时:
子节点一定被监控因此isWatched为true。
子节点可以放置或不放置相机,因此hasCamera可以为true或false。
注意当前位置放置相机,则子节点最多放置一个相机,因此一共有三种组合。
由于相机至少有一个,因此返回其中的最小值+1。 - 当当前节点没有放置相机,但被父节点监控时:
左右节点一共有四种组合,分别同时将子节点的监控状态向下递归。
返回其中的最小值。 - 当当前节点没有放置相机,也没有被父节点监控,而是被子节点监控时:
子节点至少有一个相机,向下递归状态,一共有三种组合。
返回其中的最小值
然后分别调用minCam(root, true, true)和minCam(root, false, fasle),取两者中的小值,即可得到答案。
树形dp优化剪枝
上面的方法实际采用时会超时,因为我们重复了三次调用一个子树下的三种状态的minCam。
因此我们可以将三种状态下的minCam分别保存在数组中返回。
- withCam: 当前子树root有相机。
- noCamWatchedByParent: 当前子树root没有相机,被父节点监控。
- noCamWatchedBySon: 当前子树root没有相机,被子节点监控。
在每次递归时,获取数组minCam(root.left)和minCam(root.right)。
然后根据左右子节点的三个参数来计算当前节点的新的三个参数,将其返回。
Code
1 | /** |
Code
1 | /** |
968. Binary Tree Cameras
https://xuanhe95.github.io/2022/06/18/968-Binary-Tree-Cameras/