作者推荐
【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数
本文涉及知识点
LeetCode:968监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
示例 2：
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示：
给定树的节点数的范围是 [1, 1000]。
每个节点的值都是 0。
动态规划
动态规划的状态表示
Rec(root)返回int i1,i2,i3，表示后面三种情况需要的最少摄像头。 i1，表示此子树根节点有摄像头，且子树所有节点都被监控。i2，此子树根节没有摄像头，所有节点都被监控。i3，此子树根节点无摄像头，根节点无监控，除根节点外都被监控。
动态规划的转移方程
叶子节点见初始值，本部分只讨论，非叶子节点：
i3 = min(lefti2)+min(righti2)
i2 ,左节点i1，右节点i1或i2 。或右节点i1，左节点i1,i2不存在。如果右节点不存在，则左节点i1。如果左节点不存在，则右节点i1。
i1 1 + min(lefti1,lefti2,lefti3)+min(righti1,righti2,righti3)
如果当前节点增加摄像头，则左右子树，无轮是否存在，i1,i2,i3 全部是i1。
如果当前节点没摄像头
a，一个子树i1，另外一个子树i1,i2或不存在，都是i2。
b，一个字树i1，另外一个字树i3不合法。
c，没有子树i1。两者都i2。就是i3。
动态规划的初始值
叶子节点i1,i2,i3分别为：1, 1000,0 。 1000或更大的数，表示这种可能不存在。
动态规划的填表顺序
树的先序遍历
动态规划的返回值
root的i1。
代码
核心代码
class Solution {
public:
int minCameraCover(TreeNode* root) {
const auto [i1,i2,i3] = Rec(root);
return max(1, min(i1, i2));
}
std::tuple<int, int,int> Rec(TreeNode* root)
{
if ((nullptr == root->left) && (nullptr == root->right))
{
return std::make_tuple(1, 1000, 0);
}
int i3 = 0;
int i21 = 1000,i22=1000;
int i1 = 1;//
int iLeftMin = -1, iRightMin = -1;
if (nullptr != root->left)
{
auto [t1, t2,t3] = Rec(root->left);
iLeftMin = min(t1, t2);
i3 += t2;
i21 = t1;
i1 += min(t1, min(t2, t3));
}
if (nullptr != root->right)
{
auto [t1, t2, t3] = Rec(root->right);
iRightMin = min(t1, t2);
i3 += t2;
i22 = t1;
i1 += min(t1,min(t2, t3));
}
if (nullptr != root->left)
{
i22 += iLeftMin;
}
if (nullptr != root->right)
{
i21 += iRightMin;
}
const int i2 = min(i21, i22);
//assert((i1 >= i3) && (i2 >= i3 ));
std::cout << "val: " << root->val << " i1: " << i1 << " i2:" << i2 << " i3: " << i3 << std::endl;
return std::make_tuple(i1, i2,i3);
}
};
测试用例
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
int x, target;
const int null = 10000;
{
vector<int> nodes = { 1, null, 3, null, 5, null, 7, null, 9, 10, 11, null, null, 14, 15 };
auto root = NTree::Init(nodes);
Solution sln;
auto res = sln.minCameraCover(root);
Assert(res, 3);
}
{
vector<int> nodes = { 1, 2, null, 4, null, 6, null, null, 9 };
auto root = NTree::Init(nodes);
Solution sln;
auto res = sln.minCameraCover(root);
Assert(res, 2);
}
{
vector<int> nodes = { 1, 2, null, 3, 4 };
auto root = NTree::Init(nodes);
Solution sln;
auto res = sln.minCameraCover(root);
Assert(res, 1);
}
}
优化
空节点为边界条件，更简洁。
class Solution {
public:
int minCameraCover(TreeNode* root) {
const auto [i1,i2,i3] = Rec(root);
return max(1, min(i1, i2));
}
std::tuple<int, int,int> Rec(TreeNode* root)
{
if (nullptr == root )
{
return std::make_tuple(1000,0,0);
}
auto [l1,l2,l3] = Rec(root->left);
auto [r1, r2, r3] = Rec(root->right);
int i1 = 1 + min(min(l1,l2),l3) + min(min(r1, r2), r3);
int i2 = min(l1 + r2, r1 + l2);
i2 = min(i2, l1 + r1);
int i3 = l2 + r2;
return std::make_tuple(i1, i2,i3);
}
};
2023年1月版
struct CStatus
{
int m_iFillAndRootHas;// 覆盖所有节点且根节点有监控
int m_iFill;// 覆盖所有节点，根节点不一定有监控
int m_iFillChild;//覆盖子节点，不一定覆盖根节点
};
class Solution {
public:
int minCameraCover(TreeNode* root) {
CStatus stuatu = dfs(root);
return stuatu.m_iFill;
}
CStatus dfs(TreeNode* root)
{
if (nullptr == root)
{
return{ INT_MAX / 2, 0, 0 };
}
CStatus left = dfs(root->left);
CStatus right = dfs(root->right);
CStatus ret;
ret.m_iFillAndRootHas = 1 + left.m_iFillChild + right.m_iFillChild;
ret.m_iFill = min(ret.m_iFillAndRootHas, min(left.m_iFillAndRootHas+right.m_iFill,right.m_iFillAndRootHas+left.m_iFill));
ret.m_iFillChild = min(ret.m_iFillAndRootHas,left.m_iFill + right.m_iFill);
std::cout << ret.m_iFillAndRootHas << " " << ret.m_iFill << " " << ret.m_iFillChild << std::endl;
return ret;
}
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。