【LeetCode】968. Binary Tree Cameras 解题报告（C++）
2024-09-02 10:39:18
作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
题目地址：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:
- The number of nodes in the given tree will be in the range
[1, 1000]. Everynode has value 0.
题目大意
如果放置一个摄像机，能覆盖当前节点、两个孩子节点、父亲节点。求最少的放置相机的个数。
解题方法
首先分析，每种节点能被多少种方案覆盖：
- 树中间的节点可以被当前节点、两个孩子节点、父亲节点四种方式覆盖。
- 根节点，可以被当前节点、两个孩子节点三种方式覆盖。
- 如果是叶子节点，可以被当前节点和父亲节点两种方式覆盖。
综上，我们最好的方案应该是从下向上，先设置叶子节点，然后移除所有覆盖的节点；再重复这个步骤。
具体方法是：
我们定义了一个函数dfs，
- 如果这个节点是叶子节点，返回0
- 如果这个节点是叶子节点的父节点，并且这个节点应该放相机，返回1
- 如果这个节点被子节点覆盖了，并且这个节点没有相机，返回2.
对于每个节点的话，
- 如果这个节点有子节点，并且这个子节点是叶子节点（节点0），那么当前节点需要相机0；
- 如果这个节点有子节点，并且这个子节点放置了相机（节点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;
}
};
参考资料：https://leetcode.com/problems/binary-tree-cameras/discuss/211180/JavaC%2B%2BPython-Greedy-DFS
日期
2019 年 1 月 7 日 —— 新的一周开始啦啦啊
最新文章
- 了解ASP.NET MVC几种ActionResult的本质：JavaScriptResult & JsonResult
- C++中虚析构函数作用
- ASP.NET MVC系列 框架搭建（二）之仓储层的优化
- Windows 上远程访问 Unix 的 XWindow / XManager / X
- MDEV Primer
- Java 程序中的多线程
- 运用bootstrap框架的时候 引入文件的问题
- Oracle 12C 新特性之 sqlplus查看History命令
- 查看表结构命令（mysql和oracle）
- Echarts 数据视图 生成Excel的方法
- PHP 二维数组根据某个字段按指定排序方式排序
- Linux 多网卡绑定bond
- Dynamic CRM 2015学习笔记（3）oData 查询方法及GUID值比较
- Linux中的#和$区别
- python --- 05 字典 集合
- svn cleanup失败
- 《Are your lights on？》读后感
- php 获取唯一字符串与文件扩展名函数
- Uncaught (in promise) Provided element is not within a Document
- dfs.datanode.du.reserved 预留空间不生效的问题