题目地址：https://leetcode.com/problems/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、 Thenumberofnodesinthegiventreewillbeintherange[1,1000].；
2、 Everynodehasvalue0.；
题目大意
如果放置一个摄像机，能覆盖当前节点、两个孩子节点、父亲节点。求最少的放置相机的个数。
解题方法
首先分析，每种节点能被多少种方案覆盖：
1、 树中间的节点可以被当前节点、两个孩子节点、父亲节点四种方式覆盖；
2、 根节点，可以被当前节点、两个孩子节点三种方式覆盖；
3、 如果是叶子节点，可以被当前节点和父亲节点两种方式覆盖；
综上，我们最好的方案应该是从下向上，先设置叶子节点，然后移除所有覆盖的节点；再重复这个步骤。
具体方法是：
我们定义了一个函数dfs，
1、 如果这个节点是叶子节点，返回0；
2、 如果这个节点是叶子节点的父节点，并且这个节点应该放相机，返回1；
3、 如果这个节点被子节点覆盖了，并且这个节点没有相机，返回2.；
对于每个节点的话，
1、 如果这个节点有子节点，并且这个子节点是叶子节点（节点0），那么当前节点需要相机0；
2、 如果这个节点有子节点，并且这个子节点放置了相机（节点1），那么当前节点被覆盖了；
如果节点需要相机，那么对返回结果+1，并且返回1. 如果节点被覆盖了，返回2. 否则返回0.
C++代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minCameraCover(TreeNode* root) {
if (dfs(root) == State::NONE)
++ans_;
return ans_;
}
private:
enum class State {NONE = 0, COVERED = 1, CAMERA = 2};
int ans_ = 0;
State dfs(TreeNode* root) {
if (!root) return State::COVERED;
State l = dfs(root->left);
State r = dfs(root->right);
if (l == State::NONE || r == State::NONE) {
++ans_;
return State::CAMERA;
}
if (l == State::CAMERA || r == State::CAMERA) {
return State::COVERED;
}
return State::NONE;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
参考资料：https://leetcode.com/problems/binary-tree-cameras/discuss/211180/JavaC%2B%2BPython-Greedy-DFS
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发