Given a binary tree, we install cameras on the nodes of the tree.
Each camera at a node can monitor its 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.
这道题给了一棵二叉树,说是可以在结点上放相机,可以拍父结点,自身,和左右子结点,现在问我们最少需要多少个相机才能拍到所有的结点。由于是一道 Hard 题目,博主下意识的看了一下 Related Topics,发现是 DP。于是博主就开始思考如何定义 dp,并且思考状态转移方程。但是没有想出可行的解法,于是去论坛上逛了一下,发现大家用的都是贪婪算法 Greedy Algorithm,看来博主被 Topics 误导了。不过不要紧,重要的是跟着大神 lee215 一起来解题吧。这里先来考虑,到底把相机放在什么位置可以拍到最多的结点?是叶结点吗?不一定是,因为若放在叶结点,只能拍到该叶结点和其父结点两个而已。是根结点吗?也不一定,因为放在根结点,最多拍到根结点和其左右两个子结点,总共三个而已。最优解是放在叶结点的父结点上,这样最多可以拍到四个结点。所以策略应该是先找到叶结点,让后在其父结点放上相机,同时标记父结点的父结点为被拍到了。这样就有3种不同的状态,用0来表示当前结点是叶结点,1表示当前结点是叶结点的父结点,并被放置了相机,2表示当前结点的是叶结点的爷爷结点,并被相机拍到了。这里使用一个子函数,将全局变量 res 传进去,用来记录放置的相机的总个数。在递归函数中,若当前结点不存在,则返回2,空结点也可看作已经被相机拍到了。否则分别对左右子结点调用递归函数,若二者中有一个返回0了,当前结点至少有一个子结点是叶结点,需要在当前位置放一个相机,结果 res 自增1,并返回1。否则若左右子结点的返回值有一个为1,说明左右子结点中至少有一个已经被放上了相机,当前结点已经被拍到了,返回2。若都不是,则说明当前结点是叶结点,返回0。在主函数中,若对根结点调用递归的返回值是0,说明根结点是叶结点,此时没有办法,只能在叶结点上放个相机了,所以要加上1,否则不用加,参见代码如下:
class Solution {
public:
int minCameraCover(TreeNode* root) {
int res = 0;
return (helper(root, res) < 1 ? 1 : 0) + res;
}
// Return 0 if leaf, 1 if parent of leaf with camera on this node, 2 if covered without camera on this node.
int helper(TreeNode* node, int& res) {
if (!node) return 2;
int left = helper(node->left, res), right = helper(node->right, res);
if (left == 0 || right == 0) {
++res;
return 1;
}
return (left == 1 || right == 1) ? 2 : 0;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/968
类似题目:
Distribute Coins in Binary Tree
参考资料:
https://leetcode.com/problems/binary-tree-cameras/
https://leetcode.com/problems/binary-tree-cameras/discuss/211180/JavaC%2B%2BPython-Greedy-DFS
LeetCode All in One 题目讲解汇总(持续更新中...)