[LeetCode] 968. Binary Tree Cameras

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)