968. Binary Tree Cameras

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:

  1. The number of nodes in the given tree will be in the range [1, 1000].
  2. 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

https://leetcode.com/problems/binary-tree-cameras/discuss/211966/Super-Clean-Java-solution-beat-100-DFS-O(n)-time-complexity

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation